-
Notifications
You must be signed in to change notification settings - Fork 0
/
377. Combination Sum IV.cpp
41 lines (36 loc) · 1.05 KB
/
377. Combination Sum IV.cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution {
public:
int ans = 0;
/*void DP(int sum, vector<int> nums, int target, vector<int> & memo){
if(sum == target){
++ans;
return;
}else if(sum > target) return;
for(int i = 0; i < nums.size(); ++i){
sum += nums[i];
if(memo[sum] != -1){
//cout << ans;
ans += memo[sum];
}else{
DP(sum, nums, target, memo);
}
if(sum == nums[i]) memo[nums[i]] = ans;
sum -= nums[i];
}
}*/
int combinationSum4(vector<int>& nums, int target) {
/*vector<int> memo(1e3, -1);
DP(0, nums, target, memo);
return ans;*/
int n = nums.size();
vector<unsigned int> dp(target+1, 0);
dp[0] = 1;
for(int i = 1; i <= target; ++i){
for(int j = 0; j < n; ++j){
if(i >= nums[j])
dp[i] += dp[i-nums[j]];
}
}
return dp[target];
}
};