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:

1
2
3
4
5
6
7
8
9
10
11
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：O(N) 解法　

dp[i]表示的是target为i时一共的解法。
对于如果target较大的话，可以先把nums排一下序。然后在内层循环里面当i<num的时候直接break就可以了。
follow up：如果负数被允许的话，解答可能是infinite。比如[-1,1]，target为1的情况。
这个时候需要限制比如每个元素用几次之类的。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public int combinationSum4(int[] nums, int target) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int n = nums.length;
        int[] dp = new int[target + 1];
        dp[0] = 1;  
        for (int i = 0; i <= target; i++) {
            for (int num : nums) {
                if (i >= num) {
                    dp[i] += dp[i - num];
                }
            }
        }
        return dp[target];
    }
}