一、前言
今天的主题还是回溯算法，还是根据那个backtracking模板，但是今天会涉及到去重和一些小细节的问题。
二、组合总和
1、思路：
我一开始的想法就是在for循环转化为：
for(int i = 0; i < size; i++)但是这个是会陷入一个死循环，一直会在0的这个位置进行累加，所以必须使用start作为一个
一个i的初始变量，这样才能实现不同数字且相同的累加。
再有一个关键的因素终止条件：
if (sum > target){
return;
}这个如果没有，那就一直循环递归去了。
2、整体代码如下：
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
void backtracking(vector<int> &candidates, int target, int sum, int start) {
if (sum > target) {
return;
}
if (sum == target) {
result.push_back(path);
return;
}
for (int i = start; i < candidates.size(); i++) {
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, sum ,i);
sum -= candidates[i];
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
result.clear();
path.clear();
backtracking(candidates, target, 0, 0);
return result;
}
};剪枝操作，for循环的修正：
for (int i = start; i < candidates.size() && sum + candidates[i] <= target; i++)整体代码：
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
void backtracking(vector<int> &candidates, int target, int sum, int start) {
if (sum > target) {
return;
}
if (sum == target) {
result.push_back(path);
return;
}
for (int i = start; i < candidates.size() && sum + candidates[i] <= target; i++) {
sum += candidates[i];
path.push_back(candidates[i]);
backtracking(candidates, target, sum ,i);
sum -= candidates[i];
path.pop_back();
}
}
public:
vector<vector<int>> combinationSum(vector<int>& candidates, int target) {
result.clear();
path.clear();
sort(candidates.begin(), candidates.end()); // 需要排序
backtracking(candidates, target, 0, 0);
return result;
}
};
三、组合总和|||
1、思路：
我的最开始的思路并没有包括到去重的思想
导致出现了多个重复的答案,
思路图是这样的：
首先就得有一个used数组，全部设置为false然后在递归回溯过程中，涉及到了两个新的名词：树尾和树层。树层是递归的每一层，树尾就是树的深度，在这个题目当中，我们所需要去重的是数层，当前一个和后一个相同时，used为false说明没有被使用，就可以去掉这个重复的元素了，而在深度遍历中，就没有这种情况，后面为ture就说明在深度当中，就可以往下遍历了。
这里也有一个小小的剪枝操作：
(sum + candidates[i]) <= target2、整体代码如下：
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
void backtracking(vector<int>& candidates, int target, int sum, int startIndex, vector<bool>& used) {
if (sum == target) {
result.push_back(path);
return;
}
for (int i = startIndex; i < candidates.size() && (sum + candidates[i]) <= target; i++) {
// 去重
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;
path.pop_back();
sum -= candidates[i];
}
}
public:
vector<vector<int>> combinationSum2(vector<int>& candidates, int target) {
// 创建一个判定数组
vector<bool> used(candidates.size(), false);
// 需要先排序
sort(candidates.begin(), candidates.end());
backtracking(candidates, target, 0, 0, used);
return result;
}
};四、分割回文串
1、思路：
这个题目还是比较抽象的，首先来看一下这个分割的图例：
这是不断往下递归，分割，回溯，递归，分割的过程。直到size == startIndex才是停止，所以终止条件就是：
if (s.size() == startIndex)
就说明可以终止了，内部执行的语句就是：
{
result.push_back();
return;
}这里的小小的疑惑就是为什么一到最后就可以直接添加了，而不需要判断是否为回文串。
这里的判断逻辑主要是在for循环中去体现的。
（1）返回值和参数为：
void backtracking(tring &s, int startIndex)这里的startIndex就是作为切割线来使用的；
（2）终止条件刚刚说了到了，这里就不提了，然后就是进入for循环了，这里就需要加上一个判断是否为回文串的判断条件，如果是，那么就把子串添加到path中 ，这里是判断回文串函数：
// 判断回文串函数
bool isPalindrome(const string &s, int satrt, int end) {
for (int i = satrt, j = end; i < j; i++, j--) {
if (s[i] != s[j]) {
return false;
}
}
return true;
}（3）for循环里面的组成如下
// 大循环
for (int i = startIndex; i < s.size(); i++) {
// 判断是否为回文串
if (isPalindrome(s, startIndex, i)) {
path.push_back(s.substr(startIndex, i - startIndex + 1));
} else {
// 不是就继续在该树继续往下分割。
continue;
}
// 递归
backtracking(s, i + 1);
// 回溯
path.pop_back();
}现在一行分割下去，到了低，就return，然后就是从序号1开始搜索，依次进行。
1、整体代码如下：
class Solution {
private:
vector<string> path;
vector<vector<string>> result;
// startIndex就是切割线
void backtracking(string s, int startIndex) {
// 终止条件
if (startIndex == s.size()) {
result.push_back(path);
return;
}
// 大循环
for (int i = startIndex; i < s.size(); i++) {
// 判断是否为回文串
if (isPalindrome(s, startIndex, i)) {
path.push_back(s.substr(startIndex, i - startIndex + 1));
} else {
// 不是就继续在该树继续往下分割。
continue;
}
// 递归
backtracking(s, i + 1);
// 回溯
path.pop_back();
}
}
// 判断回文串函数
bool isPalindrome(const 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;
}
public:
vector<vector<string>> partition(string s) {
backtracking(s, 0);
return result;
}
};今日学习时间：2小时；
leave message:
The lights and shades, whose well-accorded strife gives all the strength and color of our life.
在我们的生活中，一切的力量和色彩，都来自苦乐的光影，以及适度的斗争。
