377 Combination Sum IV

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?

分析& 代码

是看到discuss里面的解法，因为用backtracking实在太多可能性了

思路是和https://leetcode.com/problems/climbing-stairs/

在climbing stairs里面假如有n个台阶，每次可以跨一个台阶或者两个台阶，那么它的状态转移方程是res[i] = res[i - 1] + res[i - 2]，初始化是res[0] = 1; res[1] = 1;

但是在本题中，每次不再只是可以跨一步或者两步了，每次可以跨nums数组里面的任意数字的步，而且终点不是n了，终点是target数。所以状态转移方程是

foreach possible number in nums: res[i] += res[i - each] (i - each >= 0)

而且其中等于0也没有关系我们把res[0]初始化成1就好了。

public int combinationSum4(int[] nums, int target) {
    if(nums.length == 0) {
        return 0;
    }
    Arrays.sort(nums);
    int[] res = new int[target + 1];
    res[0] = 1;
    for(int i = 1; i <= target; i++) {
        for(int num: nums) {
            if(i - num >= 0) {
                res[i] += res[i - num];
            } else {
                break;
            }
        }
    }
    return res[target];
}