93. 复原 IP 地址
思路：
这道题的难点在于如何实现字符串的切割与有效性验证。切割的方法与第131题一致，用index与i来划分切割的区间。注意：递归回溯的条件可以用逗点控制，如果逗点为3且最后一个区间的字符串也是有效的话，则找到了有效字符串，输出到res数组即可。判断字符串是否有效有以下几点：1、区间左端点小于等于右端点；2、区间不止一个元素，且首元素不能为0；3、区间的每个字符串都是在0-9之间；4、区间数值不大于255。
代码：
class Solution {
public:
vector<string> res;
bool isvaild(const 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;
}
void backtracking(string& s,int index,int pointsum)
{
if(pointsum==3)
{
if(isvaild(s,index,s.size()-1))
{
res.push_back(s);
}
return;
}
for(int i=index;i<s.size();i++)
{
if(isvaild(s,index,i))
{
s.insert(s.begin() + i + 1 , '.');
pointsum++;
backtracking(s,i+2,pointsum);
s.erase(s.begin() + i + 1);
pointsum--;
}
else
{
break;
}
}
}
vector<string> restoreIpAddresses(string s) {
if(s.size()<4||s.size()>12)return res;
backtracking(s,0,0);
return res;
}
};
78. 子集
思路：
这道题与以往题目不同的是，在每一次递归的过程中都需要收集结果，同时在下一次递归之前保存结果。
代码：
class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int>& nums,int index)
{
res.push_back(path);
if(index>=nums.size()) return ;
for(int i=index;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 res;
}
};
90. 子集 II
思路：
本题与第78题不一致的地方在于题目给定的数组中含有重复的元素，但是输出的结果在不能包含重复的组合。解体可以分为两个环节，收集子集环节与第78题一致，去重环节与第40题一致。
代码：
class Solution {
public:
vector<int> path;
vector<vector<int>> res;
void backtracking(vector<int>& nums,int index,vector<bool> used)
{
res.push_back(path);
if(index>=nums.size())return ;
for(int i=index;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 res;
}
};
