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.
Related Topics:
Dynamic Programming
Similar Questions:
// OJ: https://leetcode.com/problems/combination-sum-iv/
// Author: github.com/lzl124631x
// Time: O(NT)
// Space: O(T)
class Solution {
unordered_map<int, int> m {{0, 1}};
int dp(vector<int>& nums, int target) {
if (m.count(target)) return m[target];
int cnt = 0;
for (int n : nums) {
if (n > target) break;
cnt += dp(nums, target - n);
}
return m[target] = cnt;
}
public:
int combinationSum4(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
return dp(nums, target);
}
};// OJ: https://leetcode.com/problems/combination-sum-iv/
// Author: github.com/lzl124631x
// Time: O(NT)
// Space: O(T)
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
vector<unsigned int> dp(target + 1, 0);
dp[0] = 1;
for (int i = 1; i <= target; ++i) {
for (int n : nums) {
if (n > i) break;
dp[i] += dp[i - n];
}
}
return dp[target];
}
};