93. 复原 IP 地址
题目链接：https://leetcode.cn/problems/restore-ip-addresses/
算法思想：回溯算法。
重要的是如何切割。可以使用一个变量point_num记录下切割的次数，作为终止条件。
class Solution {
public:
vector<vector<string>> final;
vector<string> path;
bool hefa(string sub)
{
if(sub.size()>1&&sub[0] == '0')
return false;
if(sub == "")
return false;
int sub_i = atoi(sub.c_str());
if(sub_i <=255&&sub_i>=0)
return true;
return false;
}
void huisu(string &s, int start,int point_num)
{
if(point_num == 3)
{
string sub = s.substr(start, s.size()-start);
// cout<<"sub:"<<sub<<endl;
if(hefa(sub))
{
path.push_back(s);
return;
}
}
for(int i = start; i< s.size();i++)
{
string sub = s.substr(start, i-start+1);
if(!hefa(sub))
break;
point_num++;
s.insert(s.begin()+i+1, '.');
// path.push_back(sub);
huisu(s, i+2, point_num);
point_num--;
s.erase(s.begin()+i+1);
}
}
vector<string> restoreIpAddresses(string s) {
huisu(s, 0, 0);
vector<string> res;
return path;
}
};
78. 子集
https://leetcode.cn/problems/subsets/
算法思想: 回溯。
要注意收集结果的位置是每次进入for循环之前收集。
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
void huisu(vector<int>& nums, int start)
{
res.push_back(path);
if(start == nums.size())
{
return;
}
// cout<<"start:"<<start<<endl;
for(int i=start; i<nums.size();i++)
{
path.push_back(nums[i]);
huisu(nums, i+1);
path.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
huisu(nums,0);
return res;
}
};
90. 子集 II
题目链接：https://leetcode.cn/problems/subsets-ii/
算法思想：
回溯。
不包含重复元素，则需排序。
class Solution {
public:
vector<vector<int>> output;
vector<int> res;
void huisu(vector<int>& nums, int start)
{
output.push_back(res);
if(start==nums.size())
return;
for(int i=start;i<nums.size();i++)
{
if(i!=start&&nums[i]==nums[i-1])
continue;
res.push_back(nums[i]);
huisu(nums, i+1);
res.pop_back();
}
}
vector<vector<int>> subsetsWithDup(vector<int>& nums) {
sort(nums.begin(), nums.end());
huisu(nums, 0);
return output;
}
};
