377. Combination Sum IV

  • 41.7%

https://leetcode.com/problems/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
12
13
14
15
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?

解题思路

动态规划,目标为target,计算从0到target每一个的可能组合个数,然后依次计算,依次动态规划。

java

5ms, September 9, 2016
https://discuss.leetcode.com/topic/52186/my-3ms-java-dp-solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class Solution {
public int combinationSum4(int[] nums, int target) {
Arrays.sort(nums);
int[] res = new int[target+1];
for(int i=1; i<res.length; i++){
for(int num:nums){
if(num > i)
break;
else if(num == i)
res[i] += 1;
else
res[i] += res[i-num];
}
}
return res[target];
}
}

6ms, September 9, 2016
https://discuss.leetcode.com/topic/52302/1ms-java-dp-solution-with-detailed-explanation

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
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];
}
}

cpp

3ms, September 9,2016
https://discuss.leetcode.com/topic/52217/6-lines-c-dp-solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
vector<int> result(target + 1);
result[0] = 1;
for(int i=1; i<= target; ++i){
for(int x:nums){
if(i>=x)
result[i] += result[i-x];
}
}
return result[target];
}
};

python

48ms, September 9, 2016
https://discuss.leetcode.com/topic/52227/7-liner-in-python-and-follow-up-question

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution(object):
def combinationSum4(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
nums, combs = sorted(nums), [1]+[0]*target
for i in range(target+1):
for num in nums:
if num > i:break;
if num == i: combs[i] += 1
if num < i: combs[i] += combs[i-num]
return combs[target]
谢谢你,可爱的朋友。