377. Combination Sum IV (DP)

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?

My Solutions:

用一维数组dp记录，dp[i]表示目标数为i的解的个数。然后从1遍历到target，对于每一个数i，遍历nums数组。对于数组里的每一个数字n，如果i>=n, 就可以拆分， dp[i] += dp[i - n]。

比如[1,2,3], target=4。

• i=1, 只有dp[1] += dp[1-1] = dp[0]; 最终dp[1] = 1

• i=2, 可以有dp[2] += dp[1] and dp[2] += dp[0]; 最终dp[2]=1+1=2

• i=3, 3可以拆分为1+n，而n即为dp[2]；也可以拆分为2+n，n为dp[1]；也可以拆为3+n，此时n为dp[0]。把所有的情况加起来就是组成dp[3]的所有情况了。

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

Follow up questions: 如果有negative numbers，会有infinite result，因为可以不停+/-。 可以加的limitation有：限制结果的长度。