1. 題目

2. 解題思路

此題一看應(yīng)該就是需要用到動(dòng)態(tài)規(guī)劃算法，假設(shè)我們以 f[d]表示總和為 d 的元素組合的個(gè)數(shù)，首先，我們遍歷 nums 數(shù)組，

如果有 nums[i] < target，那么組合中第一個(gè)元素我們放置 nums[i]，組合中余下元素的排列總個(gè)數(shù)也就變成了子問題 f[target - nums[i]]。

如果有 nums[i] = target，那么組合中只能放置 nums[i]這一個(gè)元素。

3. 代碼實(shí)現(xiàn)

于是，我開始實(shí)現(xiàn)了第一版代碼，完全就照著上面的解題思路來寫，使用遞歸。

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {int ret = 0;for (int i = 0; i < nums.size(); ++i) {if (nums[i] < target) {ret += combinationSum4(nums, target-nums[i]);}else if (nums[i] == target) {ret += 1;}}return ret;}
};

很可惜，沒有通過全部測試用例，超時(shí)了。

超出時(shí)間限制 10 / 16 個(gè)通過的測試用例

這里，計(jì)算 f[target - nums[i]]的時(shí)候有可能存在大量重復(fù)，比如，nums=[1, 2, 3, 4], target=5，第一個(gè)元素我們放置 2 時(shí)，需要計(jì)算 f(3)。然后，如果前兩個(gè)元素我們都放置 1 時(shí)，也需要計(jì)算 f(3)。

所以，一個(gè)很自然的思路就是把已經(jīng)計(jì)算過的 f(d)記錄下來，下次遇到可以直接用。

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {static vector<int> target_ret(1001, -1);int ret = 0;for (int i = 0; i < nums.size(); ++i) {if (nums[i] < target) {int left = target - nums[i];if (target_ret[left] == -1) {target_ret[left] = combinationSum4(nums, left); }ret += target_ret[left];}else if (nums[i] == target) {ret += 1;}}return ret;}
};

于是，我定義了一個(gè)靜態(tài)數(shù)組，全部初始化為 -1，計(jì)算一個(gè) f(d) 后就把它記錄下來，下次直接使用，不用再遞歸去調(diào)用一次函數(shù)。

但是，這次直接變成解答錯(cuò)誤了。我把錯(cuò)誤的用例單獨(dú)拿出來測試，答案是對的。去網(wǎng)上一查，原來 LeetCode 會用這同一個(gè)類去測試所有的測試用例，那么我的靜態(tài)數(shù)組就會受到前一個(gè)測試用例的影響，所以，答案也就是錯(cuò)的了，此路看來也不通！

那就只能手動(dòng)遞推了，因?yàn)槲覀冏罱K要計(jì)算 f(target) ，而 f(target) 可能依賴于 f(target-1)、f(target-2)....f(1)，所以我們就從 1 開始，一個(gè)一個(gè)往后計(jì)算 f(d) 即可。

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<int> target_ret(target+1, 0);for (int j = 1; j <= target; ++j) {for (int i = 0; i < nums.size(); ++i) {if (nums[i] < j) {int left = j - nums[i];target_ret[j] += target_ret[left];}else if (nums[i] == j) {target_ret[j] += 1;}}}return target_ret[target];}
};

很不幸，還是出錯(cuò)了，看起來是整型數(shù)超出表示范圍了，一個(gè)簡單的思路是把 int 換成 unsigned int，終于成功了！

Line 16: Char 35: runtime error: signed integer overflow: 2147483647 + 1 cannot be represented in type ‘int’ (solution.cpp)
SUMMARY: UndefinedBehaviorSanitizer: undefined-behavior prog_joined.cpp:25:35

class Solution {
public:int combinationSum4(vector<int>& nums, int target) {vector<unsigned int> target_ret(target+1, 0);for (int j = 1; j <= target; ++j) {for (int i = 0; i < nums.size(); ++i) {if (nums[i] < j) {int left = j - nums[i];target_ret[j] += target_ret[left];}else if (nums[i] == j) {target_ret[j] += 1;}}}return target_ret[target];}
};

要細(xì)究為什么會越界的話，其實(shí)題目描述里特別說明了 ：

題目數(shù)據(jù)保證答案符合 32 位整數(shù)范圍。

但是這里只是說 f(target) 不會越界，我們從 1 遍歷到 target 的某個(gè)中間變量可能越界了，然后這個(gè)中間變量實(shí)際上是用不到的。

比如，nums=[2, 6, 9], target=15， f(14) 是不會用到的，但是我們也會計(jì)算它。

時(shí)間復(fù)雜度為 $O(target?nums.size())$，空間復(fù)雜度為 $O(target)$。

如果數(shù)組中存在負(fù)數(shù)的話，會存在一個(gè)包含正數(shù)和負(fù)數(shù)的序列，它們的和為 0，也就是說，可以無限添加這個(gè)序列，而和保持不變，這樣，f(target) 就是無窮的了。