LeetCode Combination Sum IV Given an integer array with all positive numbers and no duplicates, find the number of possible combinations that add up to a positive integer target. Example:

nums = [1, 2, 3]
target = 4
The possible combination ways are:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)
Note that different sequences are counted as different combinations.
Therefore the output is 7.

Follow up: What if negative numbers are allowed in the given array? How does it change the problem? What limitation we need to add to the question to allow negative numbers?

---

给定一个数组，问从数组中有放回的取若干个数字，加起来等于target的方案数有多少种。 一开始以为是和LeetCode Combination Sum是类似的，只不过数字可以重复取而已，于是快速写出了如下的DFS版本： [cpp] class Solution { private: void dfs(vector<int>& nums, int sum, int& ans) { if (sum == 0) { ++ans; return; } if (sum < 0)return; for (const auto &i : nums) { if (sum >= i) { dfs(nums, sum – i, ans); } } } public: int combinationSum4(vector<int>& nums, int target) { int ans = 0; dfs(nums, target, ans); return ans; } }; [/cpp] 悲剧的是TLE了，给了一个样例[1,2,3]，target=32，结果有181997601种之多，DFS确实吃不消。 究其原因还是因为每个数可以重复取值，如果每个数最多取一次，也就相当于0/1背包，每个数可以取或者不取，则用DP很好办： [cpp] class Solution { public: int combinationSum4(vector<int>& nums, int target) { vector<int> dp(target + 1, 0); dp[0] = 1; for (int i = 0; i < nums.size(); ++i) { // 对每个数字 for (int j = target; j >= nums[i]; –j) { dp[j] += dp[j – nums[i]]; // 取值；不取dp[j]保持不变；所以取和不取加起来就是+=dp[j-nums[i]] } } return dp[target]; } }; [/cpp] 但是这题中，每个数是可以重复取值的。因为数组中的数最小是1，所以每个数最多可以取target次，所以我们可以把0/1背包改成最多取target次的背包问题，也就是对于每个商品，我们可以尝试取1次、2次…target次。 我们可以换一种思路，假设dp[i-1]表示生成和为i-1的所有组合数，那么生成和为i的所有组合数等于所有生成和为i-nums[j]的组合数的和，即所有dp[i-nums[j]]的和。dp[i-nums[j]]表示减去nums[j]此时的组合数。 代码如下： [cpp] class Solution { public: int combinationSum4(vector<int>& nums, int target) { vector<int> dp(target + 1, 0); dp[0] = 1; for (int i = 1; i <= target; ++i) { for (int j = 0; j < nums.size(); ++j) { if (i >= nums[j])dp[i] += dp[i – nums[j]]; } } return dp[target]; } }; [/cpp] 本代码提交AC，用时3MS。仔细观察这个版本的代码和上个版本的代码，发现其实就是两层循环换了一下位置，前者求不放回的方案数，后者求放回的方案数。 如果有负数，则要限制每个数的使用次数了，因为如果有数1和-1，要生成和为0的组合数，则可以有无限种，比如[1,-1],[1,1,-1,-1]。]]>