377. Combination Sum IV (Medium)

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?

1. Then adding a num to the combination is not guaranteed to be increasing, which means I can add a huge bounch of negative nums and add a huge bounch of positive nums to achieve a target sum. eg.target=0:[-1,1],[-1,-1,1,1],[-1,-1,-1,1,1,1]...
2. We will have lots of lots of possible combinations, even infinity.
3. For example, each negative num can only be used once, etc.

Solution 1: DP O(target * n); O(target)

    /**
     * DP O(target * n); O(target)
     * dp[i] means the # of combinations that can reach sum i.
     * dp[i] = sum(dp[i - nums[j]]), where 0 <= j < nums.length, and nums[j] <= target.
     * dp[0] = 1. Think about [1], 1, where dp[1] = dp[1 - 1] = dp[0] = 1. just for recurrence calculation
     */
    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 num : nums) {
                if (num <= i) {
                    dp[i] += dp[i - num]; //Combination Sum I的“结果可重复”计数版
                }
            }
        }
        return dp[target];
    }

Follow Up:

1.去重, 实际上就是Combination Sum I 计数版

将原题解法的两个for循环颠倒，保证每个数不会被重复使用

    /**
     * follow up 1.去重, 实际上就是Combination Sum I 计数版
     * DP O(target * n); O(target)
     * dp[i] = sum(dp[i - nums[j]]), where 0 <= j < nums.length, and nums[j] <= i <= target.
     */
    public static int combinationSum4D(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }

        int[] dp = new int[target + 1];
        dp[0] = 1;
        for (int num : nums) {
            for (int i = num; i <= target; i++) {
                dp[i] += dp[i - num];
            }
        }
        return dp[target];
    }