代码随想录算法训练营day23（0116）
1.组合总和
这题跟组合的题目差异就在于可以反复使用数组里的元素，那么需要改动的其实就只有startIndex，原来需要+1，现在就不需要了，需要注意的还有回溯逻辑，除了sum==target，还有sum>target，需要return；回溯。
题目
39. 组合总和
给你一个 无重复元素 的整数数组 candidates 和一个目标整数 target ，找出 candidates 中可以使数字和为目标数 target 的 所有 不同组合 ，并以列表形式返回。你可以按 任意顺序 返回这些组合。
candidates 中的 同一个 数字可以 无限制重复被选取 。如果至少一个数字的被选数量不同，则两种组合是不同的。
对于给定的输入，保证和为 target 的不同组合数少于 150 个。
示例 1：
输入：candidates =[2,3,6,7], target =7输出：[[2,2,3],[7]] 解释： 2 和 3 可以形成一组候选，2 + 2 + 3 = 7 。注意 2 可以使用多次。 7 也是一个候选， 7 = 7 。 仅有这两种组合。
示例 2：
输入: candidates = [2,3,5], target = 8
输出: [[2,2,2,2],[2,3,3],[3,5]]
示例 3：
输入: candidates = [2], target = 1
输出: []
代码
因为逻辑上面大差不差，这里就不再次分析其思路了直接放代码。
class Solution {
public:
vector<int>path;
vector<vector<int>>result;
void backtracking(vector<int>candidates,int target,int startIndex,int sum){
if(sum==target){
result.push_back(path);
return;
}
if(sum>target) return;
for(int i=startIndex;i<candidates.size();i++){
path.push_back(candidates[i]);
sum+=candidates[i];
backtracking(candidates,target,i,sum); //注意这里是i
sum-=candidates[i];
path.pop_back();
}
}
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
backtracking(candidates,target,0,0);
return result;
}
};2.组合总和II
去重很有说法，我还是有点模糊的，没有特别通透。
题目
40. 组合总和 II
给定一个候选人编号的集合 candidates 和一个目标数 target ，找出 candidates 中所有可以使数字和为 target 的组合。
candidates 中的每个数字在每个组合中只能使用 一次 。
注意：解集不能包含重复的组合。
示例 1:
输入: candidates =[10,1,2,7,6,1,5], target =8, 输出: [ [1,1,6], [1,2,5], [1,7], [2,6] ]
示例 2:
输入: candidates = [2,5,2,1,2], target = 5, 输出: [ [1,2,2], [5] ]
提示:
1 <= candidates.length <= 1001 <= candidates[i] <= 501 <= target <= 30
思路
代码随想录
这里大部分代码逻辑跟之前的组合问题一样，着重理清楚一下used数组的作用。
used数组是用来去重用的，那么这个去重怎么判断呢？如下思路，还是需要去模拟一下过程，最好自己手动画图理解。
如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]。
此时for循环里就应该做continue的操作。
这块比较抽象，如图：
我在图中将used的变化用橘黄色标注上，可以看出在candidates[i] == candidates[i - 1]相同的情况下：
- used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
- used[i - 1] == false，说明同一树层candidates[i - 1]使用过
可能有的录友想，为什么 used[i - 1] == false 就是同一树层呢，因为同一树层，used[i - 1] == false 才能表示，当前取的 candidates[i] 是从 candidates[i - 1] 回溯而来的。
而 used[i - 1] == true，说明是进入下一层递归，去下一个数，所以是树枝上，如图所示：
代码
class Solution {
public:
vector<vector<int>>result;
vector<int>path;
void backtracking(vector<int>candidates,int target,int sum,int startIndex,vector<bool>used){
if(sum==target){
result.push_back(path);
return;
}
if(sum>target) return;
for(int i=startIndex;i<candidates.size();i++){
// used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
// used[i - 1] == false，说明同一树层candidates[i - 1]使用过
// 要对同一树层使用过的元素进行跳过
if(i>0&&candidates[i]==candidates[i-1]&&used[i-1]==false){
continue;
}
path.push_back(candidates[i]);
sum+=candidates[i];
used[i]=true;
backtracking(candidates,target,sum,i+1,used);
used[i]=false;
sum-=candidates[i];
path.pop_back();
}
}
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
path.clear();
result.clear();
sort(candidates.begin(),candidates.end());
vector<bool>used(candidates.size(),false); //记得初始化
backtracking(candidates,target,0,0,used);
return result;
}
};3.分割回文串
很难想到，很妙，理解上面也不是特别难的那种，但是就是不太好思考到这么多点。
对于字符串的操作也没有数组那么得心应手，需要加强。
题目
131. 分割回文串
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是
回文串
。返回 s 所有可能的分割方案。
示例 1：
输入：s = "aab" 输出：[["a","a","b"],["aa","b"]]
示例 2：
输入：s = "a" 输出：[["a"]]
提示：
1 <= s.length <= 16s仅由小写英文字母组成
思路
代码随想录
本题我们面对两个难点：1.判断回文字符串。2.如何切割
对于判断，脑袋灵活一点，自己写一个函数去判断就好了，但是这个切割就有点说法了。
我们要怎么达到目的呢？往组合问题上面靠，会发现，其实切割跟组合差不多。
所以切割问题，也可以抽象为一棵树形结构，如图：
递归用来纵向遍历，for循环用来横向遍历，切割线（就是图中的红线）切割到字符串的结尾位置，说明找到了一个切割方法。
此时可以发现，切割问题的回溯搜索的过程和组合问题的回溯搜索的过程是差不多的。
此时我们进行回溯三部曲。
1.回溯函数参数与返回值
默认还是void，然后还是需要两个全局数组，字符串数组，path跟result。参数，字符串肯定需要传进来，然后就是防止重复切割需要的startIndex。
vector<vector<string>> result;
vector<string> path; // 放已经回文的子串
void backtracking (const string& s, int startIndex) {2.回溯函数终止条件
我们的startIndex其实就像是上图里的分割线，我们也是需要利用它对字符串进行切割形成子串的操作的。因此，当我们分割线达到字符串长度时，肯定就要终止了，但是，注意path数组操作不像组合里了，里面是只放回文子串。
void backtracking (const string& s, int startIndex) {
// 如果起始位置已经大于s的大小，说明已经找到了一组分割方案了
if (startIndex >= s.size()) {
result.push_back(path);
return;
}
}3.回溯函数单层搜索
首先需要写一个判断回文的函数
bool isHuiwen(string s,int start,int end){
for(int i=start,j=end;i<j;i++,j--){
if(s[i]!=s[j]){
return false;
}
}
return true;
}然后，肯定是for循环，但是要对子串的切割单独分出来，这个考验一点字符串的操作
for (int i = startIndex; i < s.size(); i++) {
if (isPalindrome(s, startIndex, i)) { // 是回文子串
// 获取[startIndex,i]在s中的子串
string str = s.substr(startIndex, i - startIndex + 1);
path.push_back(str);
} else { // 如果不是则直接跳过
continue;
}
backtracking(s, i + 1); // 寻找i+1为起始位置的子串
path.pop_back(); // 回溯过程，弹出本次已经添加的子串
}代码
class Solution {
public:
vector<string>path;
vector<vector<string>>result;
void backtracking(string s,int startIndex){
if(startIndex==s.size()){
result.push_back(path);
return;
}
for(int i=startIndex;i<s.size();i++){
if(isHuiwen(s,startIndex,i)){
string str=s.substr(startIndex,i-startIndex+1);
path.push_back(str);
}
else continue;
backtracking(s,i+1);
path.pop_back();
}
}
bool isHuiwen(string s,int start,int end){
for(int i=start,j=end;i<j;i++,j--){
if(s[i]!=s[j]){
return false;
}
}
return true;
}
vector<vector<string>> partition(string s) {
path.clear();
result.clear();
backtracking(s,0);
return result;
}
};