代码随想录算法训练营第二十四天|LeetCode93. 复原 IP 地址，LeetCode78. 子集，LeetCode90. 子集 II

LeetCode93. 复原 IP 地址

题目链接：93. 复原 IP 地址 – 力扣（LeetCode） 文章讲解：代码随想录 视频讲解：回溯算法如何分割字符串并判断是合法IP？| LeetCode：93.复原IP地址_哔哩哔哩_bilibili

思路：这道题和上一题很像，大体思路是一致的，只不过终止条件是有三个'.'就会终止。所以我们专门设定了一个pointsum用于记录所有的'.'的个数，在之后没切一段就加一，直到三就终止，然后在for循环的逻辑中需要用字符串的insert函数加入'.'，再pointsum++，然后再递归的时候需要注意不再是i+1而是i+2因为多加入了一个'.'。然后isValid()函数，需要判断每个小字符串是否合理，主要是判断一下小串开头是否为0，是否有不在0-9范围内的字符，以及数字是否大于255。

代码：

class Solution {
public:
vector<string>result;
void backtracking(string& s,int startindex,int pointsum){
if(pointsum==3){
if(isValid(s,startindex,s.size()-1)){
result.push_back(s);
}
}
for(int i=startindex;i<s.size();i++){
if(isValid(s,startindex,i)){
s.insert(s.begin()+i+1,'.');
pointsum+=1;
backtracking(s,i+2,pointsum);
s.erase(s.begin()+i+1);
pointsum-=1;
}
else{
break;
}
}
}
bool isValid(string& s,int start,int end){
if(start>end){
return false;
}
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;
}
vector<string> restoreIpAddresses(string s) {
backtracking(s,0,0);
return result;
}
};

LeetCode78. 子集

题目链接：78. 子集 – 力扣（LeetCode） 文章讲解：代码随想录 视频讲解：回溯算法如何分割字符串并判断是合法IP？| LeetCode：93.复原IP地址_哔哩哔哩_bilibili

思路：和之前组合的题目很像，只不过将path保存到结果中的指令的位置变了，不在终止条件里，而是在每次调用这个函数的时候都保存一次。如果在树中体现就是之前是只有叶子节点才保存结果，现在是每个节点都会保存。

代码：

class Solution {
public:
vector<vector<int>>result;
vector<int>path;
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();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
backtracking(nums,0);
return result;
}
};

LeetCode90. 子集 II

题目链接：90. 子集 II – 力扣（LeetCode） 文章讲解：代码随想录 视频讲解：回溯算法解决子集问题，如何去重？| LeetCode：90.子集II_哔哩哔哩_bilibili

思路：这道题没什么好说的，主要还是去重，其中去重的步骤和40.组合总和II是一模一样的。

代码：

class Solution {
public:
vector<int>path;
vector<vector<int>>result;
void backtracking(vector<int>& nums,int startindex,vector<bool>& used){
result.push_back(path);
if(startindex>=nums.size()){
return;
}
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();
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
vector<bool>used(nums.size(),false);
sort(nums.begin(),nums.end());
backtracking(nums,0,used);
return result;
}
};