0%

leetcode Combination Sum IV

leetcode 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?

题目地址:leetcode Combination Sum IV

题意:给定一个元素互不相同且均为正数的数组,让你用该数组中的数组合成target(可以重复使用),问有多少种。

思路:DP可以有两种

  • dp[i] += dp[i-num]
  • dp[i+num] += dp[i]

其实和 322 Coin Change 那题差不多。。。

第一种DP

C++

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

Java

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

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def combinationSum4(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
dp = [1] + [0] * target
for i in xrange(1, target + 1):
for x in nums:
if i >= x:
dp[i] += dp[i - x]
return dp[target]

 

第二种DP C++

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

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
public class Solution {
public int combinationSum4(int[] nums, int target) {
int[] dp= new int[target+1];
dp[0] = 1;
for(int i = 0; i < target;i++){
for(int num:nums){
if(i + num <= target) dp[i + num] += dp[i];
}
}
return dp[target];
}
}

Python

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution(object):
def combinationSum4(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
dp = [1] + [0] * target
for i in xrange(target + 1):
for x in nums:
if i + x <= target:
dp[i + x] += dp[i]
return dp[target]

 

本题是leetcode 377 Combination Sum IV题解

更多题解可以查看:https://www.hrwhisper.me/leetcode-algorithm-solution/

请我喝杯咖啡吧~