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.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
int dp[1001];
public:
int combinationSum4(vector<int>& nums, int target) {
memset(dp, -1, sizeof(dp));
dp[0] = 1;
sort(nums.begin(), nums.end());
return dfs(nums, target);
}
int dfs(vector<int>& nums, int target) {
if(dp[target] != -1) return dp[target];
dp[target] = 0;
for(int i = 0; i < nums.size() and nums[i] <= target; i++)
dp[target] += dfs(nums,target - nums[i]);
return dp[target];
}
};
|
