problem
solution
- dfs , TLE
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public:
int ret = 0;
void dfs(vector<int> & nums, int target, vector<int> & path, int s){
if(target<0) return;
if(target==0) {
ret++;
return;
}
for(int i=0;i<nums.size();++i){
path.push_back(nums[i]);
dfs(nums, target-nums[i], path, i);
path.pop_back();
}
}
int combinationSum4(vector<int>& nums, int target) {
vector<int> path;
dfs(nums, target, path,0);
return ret;
}
};option 1 - dp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution {
public:
int combinationSum4(vector<int>& nums, int target) {
int n= nums.size();
vector<unsigned long long> dp(target+1,0);
dp[0] = 1;
for(int i=1;i<=target;++i){
for(auto a:nums){
if(i>=a ) dp[i] += dp[i-a];
}
}
return dp.back();
}
};