377 Combination Sum IV

377. Combination Sum IV

1. Question

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?

2. Implementation

(1) DP

思路: 每个nums的元素都可以不停地被用，很明显的完全背包类问题，按照模板写就好了。至于follow-up，如果允许负数的话，我们无法确定最后有多少种combination得到target. 如果要加条件使得我们在有负数的情况下得到target的话，我觉得应该是每个数只能用一次。

class Solution {
    public int combinationSum4(int[] nums, int target) {
        int[] dp = new int[target + 1];
        dp[0] = 1;

        for (int j = 0; j <= target; j++) {
            for (int i = 0; i < nums.length; i++) {
                if (nums[i] <= j) {
                    dp[j] += dp[j - nums[i]];
                }
            }
        }
        return dp[target];
    }
}

3. Time & Space Complexity

时间复杂度O(n * target), 空间复杂度O(target)