377. Combination Sum IV
Given an array of distinct integers nums
and a target integer target
, return the number of possible combinations that add up to target
.
The test cases are generated so that the answer can fit in a 32-bit integer.
Example 1:
Input: nums = [1,2,3], target = 4
Output: 7
Explanation:
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.
Example 2:
Input: nums = [9], target = 3
Output: 0
Constraints:
1 <= nums.length <= 200
1 <= nums[i] <= 1000
All the elements of
nums
are unique.1 <= target <= 1000
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?
Solution:
Version 1: DP
backPack VI 和combination sum IV是同一题 本质上是背包问题,但是和BP IV又不一样,因为同一组数可以组成不同的组合 比如1, 1, 2和1, 2, 1在本题是两个解,所以j循环要放在外面,使得相同的一组数 有可能出现在不同的结果中
典型的完全背包问题(518. Coin Change 2)。 如果 数相同 顺序不同 被认为是 不同 的答案,那么就先循环背包容量,再循环物品。 如果 数相同 顺序不同 被认为是 相同 的答案,那么就先循环物品,再循环背包容量。
所以只要把(BP IV)中j循环翻出来即可: BP IV: for num in nums: for j in range(num, target + 1): dpj += dpj - num
BP VI: for j in range(1, target + 1): for num in nums: if num > j: continue dpj += dpj - num
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][n+1];
//dp[0][...] = 0;
// dp[..][0] = 1;
for(int i = 0; i<=n; i++)
{
dp[0][i] = 1;
}
for(int i = 1; i<= target; i++)
{
for(int j = 1; j<= n; j++)
{
if(i- nums[j-1] >=0)
{
// 注意这里最后是dp[i- nums[j-1]][n]
dp[i][j] = dp[i][j-1] + dp[i- nums[j-1]][n];
}
else
{
dp[i][j] = dp[i][j-1];
}
}
}
return dp[target][n];
}
}
Version 2: Top down dfs+ memorization search (similar as other combination sum)
class Solution {
public int combinationSum4(int[] nums, int target) {
int result = 0;
Arrays.sort(nums);
Map<Integer, Integer> memo = new HashMap<Integer, Integer>();
result = dfs(target, nums, 0, memo);
return result;
}
public int dfs(int count, int[] nums, int startIndex, Map<Integer, Integer> memo)
{
if(memo.containsKey(count))
{
return memo.get(count);
}
if(count == 0)
{
return 1;
}
if(count < 0)
{
return 0;
}
if(startIndex == nums.length)
{
return 0;
}
int result = 0;
for(int i = startIndex; i< nums.length; i++)
{
if(nums[i] > count) continue;
result += dfs(count-nums[i], nums, startIndex, memo);
}
memo.put(count, result);
return result;
}
}
Last updated
Was this helpful?