Combination Sum IV

Description

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?

Train of Thought

画出树形图, 对target来说, 每次都取array里的数字, 之后减去得到新的target, 直到为0 发现有很多重复计算, 所以用DP dp[target + 1] 代表target为i时需要的count

Follow Up 如果允许有负数的话就必须要限制每个数能用的次数了, 不然的话就会得到无限大的排列方式, 比如1, -1, target = 1;

Code

//recursion
public int combinationSum4(int[] nums, int target) {
if (target == 0) {
    return 1;
}
int res = 0;
for (int i = 0; i < nums.length; i++) {
    if (target >= nums[i]) {
        res += combinationSum4(nums, target - nums[i]);
    }
}
return res;
}

//bottom-up dp
public int combinationSum4(int[] nums, int target) {
    int[] comb = new int[target + 1];
    comb[0] = 1;
    for (int i = 1; i < comb.length; i++) {
        for (int j = 0; j < nums.length; j++) {
            if (i - nums[j] >= 0) {
                comb[i] += comb[i - nums[j]];
            }
        }
    }
    return comb[target];
}

Complexity