前言
更详细的在大佬的代码随想录 (programmercarl.com)
本系列仅是简洁版笔记，为了之后方便观看
子集类问题可以不写终止条件
分割回文串
题目
给你一个字符串 s，请你将 s 分割成一些子串，使每个子串都是 回文串 返回 s 所有可能的分割方案。
思考结果
切割线:startIndex
截取的子串:[startIndex,i]
代码
class Solution {
private:
vector<vector<string>> result;//二维数组
vector<string>path;//定义一维数组
bool istrue(const string&s,int start,int end )//判断是不是回文
{
for(int i=start,j=end;i<j;i++,j--)//双指针法
{
if(s[i]!=s[j]){
return false;
}
}
return true;
}
void backtracking(const string&s,int startIndex){
if(startIndex>=s.size()){//结束条件
result.push_back(path);
return ;
}
for(int i=startIndex;i<s.size();i++){//从分割线开始
if(istrue(s,startIndex, i)){//是回文子串
string str=s.substr(startIndex,i-startIndex+1);//分割串的范围是[startIndex,i]
path.push_back(str);
}
else { // 不是回文，跳过
continue;
}
backtracking(s, i + 1); //i+1为起始位置的回文子串
path.pop_back(); //回溯
}
}
public:
vector<vector<string>> partition(string s) {
result.clear();
path.clear();
backtracking(s, 0);
return result;
}
};复原IP地址
pointNum记录逗号数量，pointNum=3说明此时有四个串
i+2的原因是在字符串中加入了分隔符
.
class Solution {
private:
vector<string>result;
void backtracking( string& s,int startIndex,int pointnum){
if(pointnum==3){
if(isvalid(s,startIndex,s.size()-1)){
result.push_back(s);
return ;
}
}
for (int i = startIndex; i < s.size(); i++) {
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;
}
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;
}
};子集
不同点：和之前学过的例子相比较，每一层递归里面都有自己需要的结果
终点状态：剩余集合是空集合
终止条件可以不加:因为如果大于了数组的大小，for循环不会进入进去，直接return
注意：把收获结果放在终止条件之前，不然会省略掉最后的结果
class Solution {
private:
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();
}
}
public:
vector<vector<int>> subsets(vector<int>& nums) {
result.clear();
path.clear();
backtracking(nums, 0);
return result;
}
};子集II
原集合有重复元素但不能有重复子集
去重步骤：先排序，树层去重，树枝上不去重
if (i > 0 && nums[i] == nums[i - 1] && used[i - 1] == false) {
continue;
} bool数组定义
vector<bool> used(nums.size(), 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++) {
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;
}
};子集、组合、分割问题的的区别
子集：收集树形结构中树的所有节点的结果。
组合、分割问题：收集树形结构中叶子节点的结果。
递增子序列
给定一个整型数组, 你的任务是找到所有该数组的递增子序列，递增子序列的长度至少是2。
排序做法不可取：改变了元素的顺序
去重+非递减
unordered_set<int> uset;
if ((!path.empty() && nums[i] < path.back())|| uset.find(nums[i]) != uset.end())
{
continue;
}总代码
class Solution {
private:
vector<vector<int>> result;
vector<int> path;
void backtracking(vector<int>& nums, int startIndex) {
if (path.size() > 1) {//题意说大小要大于2
result.push_back(path);
}//不加return，因为它也属于子集问题
unordered_set<int> used; // 每一次递归都要记录 仅是对于本层进行去重
for (int i = startIndex; i < nums.size(); i++) {
if ((!path.empty() && nums[i] < path.back())|| used.find(nums[i]) !=used.end())
continue;
used.insert(nums[i]); //本层已经用过该元素了
path.push_back(nums[i]);//添加元素
backtracking(nums, i + 1);//递归到下一层
path.pop_back();//返回
}
}
public:
vector<vector<int>> findSubsequences(vector<int>& nums) {
backtracking(nums, 0);
return result;
}
};
