题目要求
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?
有一个不包含重复值的正整数数组 nums，问从数组中选择几个数，其和为 target，这样的数的组合有几种？
思路一：自顶向下的 dp
这题本质上需要注意一点，就是我如果需要组成 target，那么一定是由 nums 中的一个值和另一个值的排列组合结果构成的。比如 com[4] = com[4-1] + com[4-2] + com[4-1]。通过这一点，我们构成一个递归表达式，但是因为单纯的递归表达式没有计算中间结果，所以会造成大量重复的计算影响效率，所以这里采用 dp 的思路额外的用数组来记录已经计算过的 com 结果。比如 com[3] = com[2] + com[1], com[2] = com[1]，如果没有 dp，则需要重复计算 com[1] 的结果。
public int combinationSum4(int[] nums, int target) {
if (nums == null || nums.length < 1) {
return 0;
}
int[] dp = new int[target + 1];
Arrays.fill(dp, -1);
dp[0] = 1;
return helper(nums, target, dp);
}
private int helper(int[] nums, int target, int[] dp) {
if (dp[target] != -1) {
return dp[target];
}
int res = 0;
for (int i = 0; i < nums.length; i++) {
if (target >= nums[i]) {
res += helper(nums, target – nums[i], dp);
}
}
dp[target] = res;
return res;
}
思路二：自底向上 dp
public int combinationSum4(int[] nums, int target) {
Arrays.sort(nums);
int[] combinationCount = new int[target+1];
combinationCount[0] = 1;
for(int i = 1 ; i<=target ; i++) {
for(int j = 0 ; j<nums.length && nums[j] <= i ; j++) {
combinationCount[i] += combinationCount[i – nums[j]];
}
}
return combinationCount[target];
}