一、前言：
参考文献：代码随想录
今天的主题内容是回溯算法，这一章的干货很多，我需要慢慢的品味，不单单只是表象，还需要研究深层原理。
二、复原IP地址
1、思路：
（1）首先还是确定返回值和参数：
void backtracking(string &s, int startIndex, int pointSum)这里比往常多了一个pointSum，这个是来判断是否符合ip格式的一个标志，也就是记录这个s中存在多少个"."；
（2）终止条件如下：
// pointsum是用来判断这个字符串中存在多少个"."如果有了三个，就说明满足IP格式了
if (pointSum == 3) {
if (isValud(s, startIndex, s.size() - 1)) {
// 这里还有一个条件就是判断最后的一段是否符合IP要求
result.push_back(s);
}
return;
} 这里首先要判断是否有三个”.“，存在之后，再判断最后的那一段是否符合IP的格式，然后才能插入，如果不符合那就直接return回溯了。
（3）单层递归逻辑：
for (int i = startIndex; i < s.size(); i++) {
if (isValud(s, startIndex, i)) {
s.insert(s.begin() + i + 1, '.'); // 插入"."
pointSum++;
backtracking(s, i + 2, pointSum); // 这里是 i+2 此逻辑是因为加了"."需要多加一个1
// 回溯
pointSum--;
s.erase(s.begin() + i + 1); // 删除"."
} else {
break;
}
}看起来并不复杂，但是，难疑点比较多。首先就是先判断当前的这个切片处是否符合IP格式，然后再进行插入逗点，pointSum再做记录，然后就可以开始递归了，这里的是 i+2的，因为这个时候插入了逗点，所以需要后移一位，接着就是回溯了。
（4）主函数中存在一个小小的剪枝操作，如下：
if (s.size() < 4 || s.size() > 12) return result;（5）判断是否为ip的函数为：
bool isValud(string &s, int start, int end) {
if (start > end) {
return false;
}
// 头号字符不能为0（只有一位时可以）
if (s[start] == '0' && start != end) {
return false;
}
// 小于等于255
int num = 0;
for (int i = start; i <= end; i++) {
// 不为合法数字也排除
if (s[i] > '9' || s[i] < '0') {
return false;
}
num = num * 10 + (s[i] - '0');
if (num > 255) {
return false;
}
}
return true;
}这里的细节也比多：
1、start和end的比较；
2、头数字不为0，且不是只有一个数字；
3、和小于等于255；
2、整体代码如下：
class Solution {
private:
// 判断是否为合法IP
bool isValud(string &s, int start, int end) {
if (start > end) {
return false;
}
// 头号字符不能为0（只有一位时可以）
if (s[start] == '0' && start != end) {
return false;
}
// 小于等于255
int num = 0;
for (int i = start; i <= end; i++) {
// 不为合法数字也排除
if (s[i] > '9' || s[i] < '0') {
return false;
}
num = num * 10 + (s[i] - '0');
if (num > 255) {
return false;
}
}
return true;
}
vector<string> result;
void backtracking(string &s, int startIndex, int pointSum) {
// pointsum是用来判断这个字符串中存在多少个"."如果有了三个，就说明满足IP格式了
if (pointSum == 3) {
if (isValud(s, startIndex, s.size() - 1)) {
// 这里还有一个条件就是判断最后的一段是否符合IP要求
result.push_back(s);
}
return;
}
// 单层递归逻辑
for (int i = startIndex; i < s.size(); i++) {
if (isValud(s, startIndex, i)) {
s.insert(s.begin() + i + 1, '.'); // 插入"."
pointSum++;
backtracking(s, i + 2, pointSum); // 这里是 i+2 此逻辑是因为加了"."需要多加一个1
// 回溯
pointSum--;
s.erase(s.begin() + i + 1); // 删除"."
} else {
break;
}
}
}
public:
vector<string> restoreIpAddresses(string s) {
if (s.size() < 4 || s.size() > 12) return result; // 算是剪枝了
backtracking(s, 0 , 0);
return result;
}
};三、子集
1、思路：
（1）返回值和终止条件并没有什么改变：
void backtracking(vector<int> &nums, startIndex)(2)终止条件（这个条件可有可不有，因为在return时以及到了叶子节点处，循环自然就不去了，就不用手动终止了）：
if (startIndex >= nums.size()) return;（3）单层递归逻辑：
for (int i = startIndex; i < nums.size(); i++) {
// 插入元素
path.push_back(nums[i]);
// 递归
backtracking(nums, i + 1);
// 回溯
path.pop_back();
}还是插入，递归，回溯。。。
（4）最重要的就是收集path，在每次递归开始时就可以收集子集了；
2、整体代码如下：
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
void backtracking(vector<int>& nums, int startIndex) {
// 收集结果，每递归一次就可以收集一次结果
result.push_back(path);
// 终止条件，可写可不写，因为到了最后的叶子节点，自然会终止的
if (startIndex >= nums.size()) return;
for (int i = startIndex; i < nums.size(); i++) {
// 插入元素
path.push_back(nums[i]);
// 递归
backtracking(nums, i + 1);
// 回溯
path.pop_back();
}
return;
}
public:
vector<vector<int>> subsets(vector<int>& nums) {
backtracking(nums, 0);
return result;
}
};四、子集||
1、思路：
这个题目和上一题加上组合总和|||综合，这里也需要添加一个used来判断是否使用了这个元素，如果使用了那就可以继续遍历，说明在树枝上，但是如前面一个元素相同，但是没有被使用，说明在数层上面，就需要跳过这个数字了，避免重复。
图解如下：
这里就不一步步分析了；
2、整体代码如下：
class Solution {
private:
vector<int> path;
vector<vector<int>> result;
void backtracking(vector<int>& nums, int startIndex, vector<bool> &used) {
result.push_back(path);
for (int i = startIndex; i < nums.size(); i++) {
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
continue;
}
path.push_back(nums[i]);
used[i] = true;
backtracking(nums, i + 1, used);
used[i] = false;
path.pop_back();
}
return;
}
public:
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<bool> used(nums.size(), false);
sort(nums.begin(), nums.end());
backtracking(nums, 0, used);
return result;
}
};今日学习时间：2小时
leave message:
Her behavior is well-accorded with the expectations of her parents.
她的行为与父母的期望相符。
