代码随想录算法训练营第60期第二十八天打卡

       今天我们继续回溯算法章节，昨天我们重点讲的是组合问题，我们完美使用递归三部曲以及递归回溯相结合的方法来解决，当然昨天最有难度的还是去重操作，那个大家要多思考一下，那么今天我们就继续探讨回溯算法。

第一题对应力扣编号为93的题目复原IP地址

      大家是否了解IP地址呢？当然这不是重点，大家可以去计算机网络了解一下，我们先来看一下题目要求：

       题目有点复杂，首先我们要搞明白什么才是有效的IP地址，首先要求里面的四个数字介于0到255之间，不能含有前导0，不能出现其他符号，我们还不能改变原先字符串中元素的相对位置，中间要加入.号，我们思考一下应该如何做？首先我们可以猜想这道题一定要使用回溯算法，而且应该是组合问题，这个大家是否还记得昨天的题目有一道分割回文串的题目，这两道题目应该是类似的，这道题我们多了一个要求就是点号的数量需要记录否则我们就不知道递归的终止条件了，一个有效的IP地址应该是有三个点号，因此我们尝试写出代码：

class Solution {
private:vector<string> result; //存放所有可能的结果//明确递归参数是我们递归三部曲的第一步 pointNum表示的是点号的数量void backtracking(string &s, int startIndex, int pointNum){//递归的终止条件if (pointNum == 3){//如果这是一个有效的IP地址if (isValid(s, startIndex, s.size() - 1)){result.push_back(s);return;}}for (int i = startIndex; i < s.size(); ++i){//判断[startIndex, i]这一段是不是合格的IP地址if (isValid(s, startIndex, i)){//如果合格的话我们就应该添加点号s.insert(s.begin() + i + 1, '.');pointNum++;backtracking(s, i + 2, pointNum);pointNum--;s.erase(s.begin() + i + 1);}else break;}}bool isValid(const string &s, int start, int end){if (start > end) return false;//不能含有前导零但是只有0是合法的if (s[start] == '0' && start != end) return false;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;   }
public:vector<string> restoreIpAddresses(string s) {result.clear();if (s.size() < 4 || s.size() > 12) return result;backtracking(s, 0, 0);return result;}
};

       本题目代码较长而且需要考虑的事情也比较多，大家务必多注意，尤其是我判断是否是合法的IP地址的时候，我们要注意数据的范围才可以，还要注意如果我找出了一段合格的IP地址我一定要及时添加点号，其他的回溯跟递归思想其实跟以前的题目相差不大，大家多多练习就可以了。

第二题对应力扣编号为78的题目子集

       这一道题目是求子集，在数学上我们都很清楚一个集合的子集应该如何计算，我们还了解真子集等，但是我们应该如何用编程来去找数组的所有子集呢？这估计是一个棘手的问题，很明显就算我们目前不会但是我们也知道这需要使用回溯算法，那我们就一起看一下题目：

        注意一点空集是任何集合的子集，是任何非空集合的真子集，我们千万不要忘记空数组也要算进去，我们的代码可以这样写：

class Solution {
private:vector<int> path;vector<vector<int>> result;void backtarcking(const 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]);backtarcking(nums, i + 1);path.pop_back();}}
public:vector<vector<int>> subsets(vector<int>& nums) {result.clear();path.clear();backtarcking(nums, 0);return result;   }
};

       其实这跟我们原来做过的组合问题是很类似的，只不过注意最后的收获果实的时候不一样，子集我需要边判断边收集，包括一上来空集也要收集，还要注意递归的过程，一定是i+1否则会输出好多次一样的子集，这个一定要注意，大家做完题一定要反复思考，并要及时总结每一道题目的精华，这样我们的刷题才是有效的。

第三题对应力扣编号为90的题目子集II

       我们拿到这道题我们先要对比看一下跟上一道题目是不是有哪里是不一样的地方，为什么会分为两个题出，上面的题是给出的数组里没有重复的元素，但这道题目是有重复元素的，这会影响我们递归的过程，我起初没有想到有什么区别，我直接就用上一道题目的代码提交了，结果发现出现重复的子集了，我就知道了这道题目跟组合问题安排套路是一样的，其实这道题目难点就是去重，我们这就把握住题目关键点了，我还是需要给大家好好解释一下去重的过程，大家看代码随想录给出的示意图：

       我们知道回溯的操作过程就是在一棵树上进行的，我们首先要进行排序这样才有助于我们去重，否则我们有可能很难遇到相等的从而去重，我们去重不能从第一个元素去，如果第一个元素去重就会忽略虽说是一个值但是是不同的元素的情况，这点其实上面的题目体现的淋漓尽致，大家要注意，还有我们是树层去重，如果树枝去重就会去掉不应该去重的子集，尤其是存在相同元素的时候，我们其实ues[i-1] = false不就是树层去重，这样大家或许就理解了，我们从第一个元素就开始去重操作了，这样可以保证我们不漏重，接下来我们来看一下代码是如何写的：

class Solution {
private:vector<vector<int>> result;vector<int> path;void backtracking(vector<int>& nums, int startIndex, vector<bool>& used) {result.push_back(path);for (int i = startIndex; i < nums.size(); i++) {// used[i - 1] == true，说明同一树枝candidates[i - 1]使用过// used[i - 1] == false，说明同一树层candidates[i - 1]使用过// 而我们要对同一树层使用过的元素进行跳过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();}}public:vector<vector<int>> subsetsWithDup(vector<int>& nums) {result.clear();path.clear();vector<bool> used(nums.size(), false);sort(nums.begin(), nums.end()); // 去重需要排序backtracking(nums, 0, used);return result;}
};

       难点还是去重，其他的与我们上一道题目没有丝毫差别，大家要类比我们原先做过的题目，看看不一样的地方，多去总结，这道题目的递归与回溯的过程我就不讲了，其实我前面的几篇博客有讲，大家可以去看看，今天的题目我们就讲解完毕了。

今日总结

       今天的题目其实不算太难，只要前几天的掌握扎实了就不是太大问题，第一题IP地址那一道题目跟我们昨天做过的那道分割回文串的题目思路是完全一致的，只不过判断有效IP地址的方法与判断回文串的方法不一样，递归与回溯的过程是完全类似的，还有今天的两道子集的问题与我们五一假期前做过的组合问题是及其类似的，大家可以去前面复习一下，把代码独立写出来就可以了，今天的分享就到这里，我们明天再见！