0%

leetcode 377 组合总和Ⅳ

给定一个由正整数组成且不存在重复数字的数组,找出和为给定目标正整数的组合的个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
示例:
nums = [1, 2, 3]
target = 4

所有可能的组合为:
(1, 1, 1, 1)
(1, 1, 2)
(1, 2, 1)
(1, 3)
(2, 1, 1)
(2, 2)
(3, 1)

请注意,顺序不同的序列被视作不同的组合。

因此输出为 7

思路:第一想法就是暴搜,从数组的第一个数开始,搜索使用第一个数字,看能有多少种方案可以使总和恰好为target,然后继续算用以第二个数字作为第一数字能有多少种方案可以使综合恰好为target,以此类推。这种方法的弊端非常明显,如果target比数组的数都大很多的话,递归深度太深了会超时,所以果然TEL了。后面想到可以做记忆化,用ans记录总和恰好等于target的所有方案数,所以有
\(ans[target]=ans[target-current] + count\)状态转移方程。其中current表示1target之中的状态,count表示总和恰好为current时有多少种方案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
超时代码:
class Solution {
public:
int count;
int combinationSum4(vector<int>& candidates, int target) {
dfs(target,target,candidates);
return count;
}
void dfs(int target,int remain,vector<int>& candidates){
if(remain<0)return;
if(remain==0){
count++;
return;
}
for(int i = 0;i<candidates.size();i++){
dfs(target,remain - candidates[i],candidates);
}
}
};
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
加了记忆化之后的代码
class Solution {
public:
vector<long long> temp;
long long count;
int combinationSum4(vector<int>& candidates, int target) {
temp = vector(target+1,-1ll);
for(int i=1;i<=target;i++){
count=0;
dfs(i,i,candidates);
temp[i]=count;
}
return count;
}
void dfs(int target,int remain,vector<int>& candidates){
if(remain<0)return;
if(temp[remain]!=-1){//如果还要凑的数已经算过了则加上当前方案数之和返回即可。
count+=temp[remain];
count%=INT_MAX;//防止超出整数的表示范围
return;
}
if(remain==0){
count++;
return;
}
for(int i = 0;i<candidates.size();i++){
dfs(target,remain - candidates[i],candidates);
}
}
};