1、39组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
输入：candidates = [2,3,6,7], target = 7
输出：[[2,2,3],[7]]
提示：
- 2 <= candidates[i] <= 40 ==>意味着不会出现0，导致无穷多组合计；全为正意味着sum递增，不会出现一直递归下去的情况，总会遇到target边界。
我的思路：这道题和一般的组合不同。数字可以重复选取，意味着j可以从i开始，k可以从j开始，因此也不需要剪枝。另一点是这道题递归的层数并不固定，找到target就返回。 下面是组合的框架，只适用于候选元素互不相同时。
代码随想录
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
public:
void traverse(vector<int>& candidates,int startidx,int sum, int target,vector<int> &path, vector<vector<int>> &res){
if(sum > target)return;
if(sum == target){
res.emplace_back(path);
return;
}
for(int i = startidx;i<candidates.size();i++){
path.emplace_back(candidates[i]);
traverse(candidates,i,sum+candidates[i],target,path,res);
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
vector<int> path;
vector<vector<int>> res;
traverse(candidates,0,0,target,path,res);
return res;
}
};
|
2、40组合总和II
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
我的思路：和上一题39组合总和不同，这题候选元素有重复，则带重复元素的组合也会有重复。所以需要去重。另外元素不允许多次选取。
代码随想录：去重，其实就是 (单层for循环内/递归同一深度) 使用过的元素不能重复选取。我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。强调一下，树层去重的话，需要对数组排序！
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
| class Solution {
public:
void traverse(vector<int>& candidates,vector<bool> &used, int startidx,int sum, int target,vector<int> &path, vector<vector<int>> &res){
if(sum > target)return;
if(sum == target){
res.emplace_back(path);
return;
}
for(int i = startidx;i<candidates.size();i++){
if(i>0 && candidates[i]==candidates[i-1] && used[i-1]==false)continue;
used[i] = true;
path.emplace_back(candidates[i]);
traverse(candidates,used,i+1,sum+candidates[i],target,path,res);
path.pop_back();
used[i] = false;
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
vector<int> path;
vector<vector<int>> res;
vector<bool> used(candidates.size(),false);
std::sort(candidates.begin(),candidates.end());
traverse(candidates,used,0,0,target,path,res);
return res;
}
};
|
3、131分割回文串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是回文串。返回 s 所有可能的分割方案。
- 输入：s = “aab”
- 输出：[[“a”,“a”,“b”],[“aa”,“b”]]
我的思路：先用多叉树表示出分割的过程。然后使用回溯的递归框架就可以。
代码随想录
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
| class Solution {
public:
void traverse(string &s,int startidx, vector<string> &path, vector<vector<string>> &res){
if(startidx == s.size()){
res.emplace_back(path);
return;
}
for(int i = startidx;i<s.size();i++){
if(!isHuiwen(s,startidx,i))continue;
path.emplace_back(s,startidx,i-startidx+1);
traverse(s,i+1,path,res);
path.pop_back();
}
return;
}
bool isHuiwen(string &s,int start, int end){
while(start<=end){
if(s[start++]!=s[end--])return false;
}
return true;
}
vector<vector<string>> partition(string s) {
vector<string> path;
vector<vector<string>> res;
traverse(s,0,path,res);
return res;
}
};
|
代码随想录算法训练第二十九天|39组合总和|40组合总和II|131分割回文串
