Leetcode 377. 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?

Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.

Analysis:
A classic DP problem. Define dp[k + 1], where dp[i] means for the target i, how many ways do we have. So the transist function would be for each target i, we iterate all the nums, and sum up its ways.

Code (Java):

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;
        
        for (int k = 1; k <= target; k++) {
            for (int i = 0; i < nums.length; i++) {
                if (k - nums[i] >= 0) {    
                    dp[k] += dp[k - nums[i]];
                }
            }
        }
        
        return dp[target];
    }
}

最初思路：
1.刚开始拿到这道题时，高兴！这不就是 K Sum 的简单版吗？只不过成员可以重复使用。要知道，重复使用成员是可以把DP降一维的！所以果断列出了一维DP (DP[target + 1]，存DP[num] 的组合数)；
2.然后循环的时候，还是老样子，先循环 nums 中的数，再循环 1 ~ target。但是这样写，结果错了！为什么呢？假设这个 nums 数组是排好序的 (我们也可以先排个序)，那么如果这样子循环的话，我们可以看到，我们得到的所有组合中，数全都是从小到大的！比如 nums = [1,2,3,4]，target = 4，那么我们最后求出的组合为 —— {1111, 112, 22, 13, 4}，是不是漏了很多？没错，乱序组合都没有包括在内！

改进思路：
1.改进思路的1同上面的1，略；
2.然后循环的时候，先循环 1～target，再循环 nums 中的数，反过来了！为什么呢？因为这样可以保证当 target = t 的时候，其包含的组合可以以任何一个 nums 中的数结尾！
3.假设还是上例，target = 1时，只有 1，DP[1] = 1；target = 2时，循环 [1,2,3,4]，得到 {11, 2}，DP[2] = 2；然后target = 3时，得到 DP[3] = 1->DP[2] + 2->DP[1] + 3->DP[0] = 4，which 分别是 {111, 21, 12, 3}，我们可以看出，此时包括了所有的组合了，很好！以此类推。。。