代码随想录算法训练营第二十三天| 93.复原IP地址 78.子集 90.子集II

本文主要是介绍代码随想录算法训练营第二十三天| 93.复原IP地址 78.子集 90.子集II，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、LeetCode 93.复原IP地址

题目链接：LeetCode 93.复原IP地址

文章讲解：代码随想录
视频讲解：回溯算法如何分割字符串并判断是合法IP？| LeetCode：93.复原IP地址

思路：

给出一个纯数字组成的字符串，要求给字符串中加‘.’，让它成为一个合法的IP。基本的思路很简单，把数字分成四组，每组一到三个数字，判断每组的数字是否合法即可，由此思路设计回溯算法。

我们设计回溯算法的每一层递归是分的每一组数字，分别分出1 ~ 3个数字，在三叉树中进行回溯遍历；并且设计检验合法性的函数，检测数组越界、数字大小（< 256）以及不存在 0 开头的多位数。

C++代码

class Solution {
private:vector<string> ipAdds;string addr;bool ifValid(string s, int left, int len) { //判断分割是否有效if (left + len > s.size()) return false;string ip = s.substr(left, len);if (len > 1 && ip[0] == '0') return false;if (stoi(ip) > 255) return false;ip.push_back('.');  //若有效则直接存入类成员变量addr中addr += ip;return true;}void backtrack(string s, int cur) { //回溯算法if (addr.size() - cur >= 3) {if (cur < s.size() && ifValid(s, cur, s.size() - cur)) {addr.erase(addr.size() - 1);ipAdds.push_back(addr);}return;}int pre = addr.size(); //pre记录插入前位置，便于回溯返回后的复原操作for (int i = 1; i <= 3; i++) {if (ifValid(s, cur, i)) {backtrack(s, cur + i);addr.erase(pre); //回溯}}}
public:vector<string> restoreIpAddresses(string s) {if(s.size() <= 12) backtrack(s, 0);return ipAdds;}
};

二、LeetCode 78.子集

题目链接：LeetCode 78.子集

文章讲解：代码随想录
视频讲解：回溯算法解决子集问题，树上节点都是目标集和！ | LeetCode：78.子集

思路

构建子集树，可以选用二叉子集树进行遍历，即在集合中每一个元素的位置判断选还是不选，作为子集树的左右孩子；具体算法见如下代码。

C++代码

class Solution {
private:vector<vector<int>> subset;vector<int> set;vector<int> src; //传入的原集合存入类成员变量，便于递归函数传参void backtrack(int i){if(i >= src.size()){subset.push_back(set);return;}backtrack(i+1); //对应不选择的情况set.push_back(src[i]);backtrack(i+1); //选择的情况set.pop_back();}
public:vector<vector<int>> subsets(vector<int>& nums) {src = nums;backtrack(0);return subset;}
};

三、LeetCode 90.子集II

题目链接：LeetCode 90.子集II

文章讲解：代码思想录
视频讲解：回溯算法解决子集问题，如何去重？| LeetCode：90.子集II

思路

这一个子集题目与上一题不同的是集合中含有重复元素，因此涉及到去重操作。去重问题我们在前面的组合数问题中也遇到过，使用 n 叉树中同一树层的数字操作进行去重。本题笔者偏好于使用二叉子集树，因此去重方法有一些不同。

借鉴力扣官方题解与灵茶山艾府大佬的题解，在选择子集的过程中，考虑数组 [1,2,2]，选择前两个数，或者第一、三个数，都会得到相同的子集。

也就是说，对于当前选择的数 x，若前面有与其相同的数 y，且没有选择 y，此时包含 x 的子集，必然会出现在包含 y 的所有子集中。

我们可以通过判断这种情况，来避免生成重复的子集。代码实现时，可以先将数组排序；迭代时，若发现没有选择上一个数，且当前数字与上一个数相同，则可以跳过当前生成的子集。

这个跳过的过程可以使用一个while循环来实现，可以节省一部分时间和空间，提高效率。

C++代码

class Solution {
private:vector<vector<int>> subsets;vector<int> set;vector<int> src;void backtrack(int i){ //二叉子集树，若当前数字不选且后面数字相同，那么跳过if(i >= src.size()){subsets.push_back(set);return;}set.push_back(src[i]); //当前数字选择1，即选择加入子集backtrack(i+1);set.pop_back();//不选当前数就跳过后面一样的数while(i+1 < src.size() && src[i+1] == src[i]){i++;}backtrack(i+1);}
public:vector<vector<int>> subsetsWithDup(vector<int>& nums) {sort(nums.begin(), nums.end());src = nums;backtrack(0);return subsets;}
};