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.
Approach #1: DFS. [C++] (TLE)
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
int ans = 0;
dfs(nums, ans, target, 0);
return ans;
}
private:
void dfs(const vector<int>& nums, int& ans, const int target, int curval) {
if (curval > target) return ;
if (curval == target) ans++;
for (int i = 0; i < nums.size(); ++i) {
dfs(nums, ans, target, curval+nums[i]);
}
}
};
Approach #2: Recursive With Memoization. [C++]
class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
// memo.resize(target+1, 0);
memo = vector<int>(target + 1, -1);
memo[0] = 1;
return dp(nums, target);
}
private:
vector<int> memo;
int dp(const vector<int>& nums, int target) {
if (target < 0) return 0;
if (memo[target] != -1) return memo[target];
int ans = 0;
for (int num : nums)
ans += dp(nums, target-num);
return memo[target] = ans;
}
};
Approach #3: DP. [C++]
int combinationSum4(vector<int>& nums, int target) {
vector<int> dp(target+1, 0);
dp[0] = 1;
for (int i = 1; i <= target; ++i) {
for (const int num : nums) {
if (i-num >= 0)
dp[i] += dp[i-num];
}
}
return dp[target];
}
Reference:
http://zxi.mytechroad.com/blog/dynamic-programming/leetcode-377-combination-sum-iv/
原文：https://www.cnblogs.com/ruruozhenhao/p/10393554.html