Description
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?
Credits:
Special thanks to @pbrother for adding this problem and creating all test cases.
Solution
Recursion with memo
由于本题是顺序相关的，其实应该是permutation而非combination，用memo以避免重复计算子问题。
用DP也可以解。
class Solution {
public int combinationSum4(int[] nums, int target) {
return combinationSum4Recur(nums, target, new HashMap<>());
}
public int combinationSum4Recur(int[] nums, int target, Map<Integer, Integer> map) {
if (target == 0) {
return 1;
}
if (target < 0) {
return 0;
}
if (map.containsKey(target)) {
return map.get(target);
}
int count = 0;
for (int n : nums) {
count += combinationSum4Recur(nums, target - n, map);
}
map.put(target, count);
return count;
}
}
Follow-up
如果array中有负数，则需要给定一个combination maximum length，用来终止递归。
