创作不易，感谢三连支持！！
一、全排列I
class Solution {
public:
//全局变量
vector<vector<int>> ret;
vector<int> path;
bool check[6];
vector<vector<int>> permute(vector<int>& nums)
{
dfs(nums);
return ret;
}
void dfs(vector<int>& nums)
{
if(nums.size()==path.size()) {ret.push_back(path); return;}
for(int i=0;i<nums.size();++i)
{
if(check[i]==false) //说明没选过
{
path.push_back(nums[i]);
check[i]=true;//减枝
dfs(nums);//继续去下一个找
//回溯
path.pop_back();
check[i]=false;
}
}
}
};二、全排列II
方案1：不合法就continue
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
bool check[8];
vector<vector<int>> permuteUnique(vector<int>& nums)
{
sort(nums.begin(),nums.end());
dfs(nums);
return ret;
}
void dfs(vector<int>& nums)
{
if(nums.size()==path.size()) {ret.push_back(path);return;}
//思路1：考虑不合法的选择 continue 思路2：考虑合法的才进dfs
for(int i=0;i<nums.size();++i)
{
if(check[i]==true||(i!=0&&nums[i]==nums[i-1]&&check[i-1]==false)) continue;
path.push_back(nums[i]);
check[i]=true;
dfs(nums);//去下一层找
path.pop_back();
check[i]=false;
}
}
};方案2：合法才能进循环
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
bool check[8];
vector<vector<int>> permuteUnique(vector<int>& nums)
{
sort(nums.begin(),nums.end());
dfs(nums);
return ret;
}
void dfs(vector<int>& nums)
{
if(nums.size()==path.size()) {ret.push_back(path);return;}
//思路1：考虑不合法的选择 continue 思路2：考虑合法的才进dfs
for(int i=0;i<nums.size();++i)
{
if(check[i]==false&&(i==0||nums[i]!=nums[i-1]||check[i-1]==true))
{
path.push_back(nums[i]);
check[i]=true;
dfs(nums);//去下一层找
path.pop_back();
check[i]=false;
}
}
}
};三、优美的排列
class Solution {
public:
//类似全排列，可以交换位置但是不能重复
int ret=0;
bool check[16];
int countArrangement(int n)
{
dfs(1,n);
return ret;
}
void dfs(int pos,int n)
{
if(pos==n+1) {++ret;return;}
for(int i=1;i<=n;++i)
{
if(check[i]==false&&(i%pos==0||pos%i==0))
{
check[i]=true;
dfs(pos+1,n);
check[i]=false;
}
}
}
};
四、子集I
策略1：决策树以选不选作为参考，结果为叶子节点
class Solution {
public:
//设置全局变量
vector<vector<int>> ret;
vector<int> path;//记录路径
public:
vector<vector<int>> subsets(vector<int>& nums)
{
dfs(nums,0);
return ret;
}
void dfs(vector<int>& nums,int pos)
{
if(pos==nums.size()) { ret.push_back(path); return;}
//选
path.push_back(nums[pos]);
dfs(nums,pos+1);
path.pop_back();//回溯
//不选
dfs(nums,pos+1);
}
};策略2：决策树以选几个为参考，结果为全部节点
class Solution {
public:
//设置全局变量
vector<vector<int>> ret;
vector<int> path;
public:
vector<vector<int>> subsets(vector<int>& nums)
{
dfs(nums,0);
return ret;
}
void dfs(vector<int>& nums,int pos)
{
ret.push_back(path);//每一个决策都是结果
for(int i=pos;i<nums.size();++i)
{
path.push_back(nums[i]);
dfs(nums,i+1);
path.pop_back();
}
}
};五、子集II
class Solution {
public:
vector<vector<int>> ret;
vector<int> path;
vector<vector<int>> subsetsWithDup(vector<int>& nums)
{
sort(nums.begin(), nums.end());
dfs(nums,0);
return ret;
}
void dfs(vector<int>& nums,int pos)
{
ret.push_back(path);
for(int i=pos;i<nums.size();++i)
{
if(i>pos&&nums[i]==nums[i-1]) continue;
path.push_back(nums[i]);
dfs(nums,i+1);
path.pop_back();
}
}
};六、找出所有子集的异或总和再求和
class Solution {
int sum=0;//记录总和
int path=0;//记录路径
public:
int subsetXORSum(vector<int>& nums)
{
dfs(nums,0);
return sum;
}
void dfs(vector<int>& nums,int pos)
{
sum+=path;
for(int i=pos;i<nums.size();++i)
{
path^=nums[i];
dfs(nums,i+1);
path^=nums[i];//利用消消乐的性质恢复现场
}
}
};七、字母大小写全排列
class Solution {
public:
vector<string> ret; //找返回值
vector<string> letterCasePermutation(string s)
{
dfs(s,0);
return ret;
}
void dfs(string s,int pos)//用传值s 可以直接在原来的s上进行修改
{
while(pos<s.size()&&isdigit(s[pos])) ++pos;
if(pos==s.size()) {ret.push_back(s); return;}
//变
s[pos]^=32; //^=32(空格)可以完成大小写转化！！
dfs(s,pos+1);
s[pos]^=32;
//不变
dfs(s,pos+1);
}
};八、下一个排列
class Solution {
public:
void nextPermutation(vector<int>& nums)
{
if(nums.size()==1) return;//如果只有一个数，就没有必要去修改了
//思路，找尽可能靠右的低位，与一个尽可能小的大数交换 然后再升序后面的剩余元素
for(int i=nums.size()-2;i>=0;--i)
{
if(nums[i]<nums[i+1])
{
for(int j=nums.size()-1;j>i;--j)
{
if(nums[i]<nums[j]) //找到第一个比i大，
{
swap(nums[i],nums[j]);
sort(nums.begin()+i+1,nums.end());//i位置后面的数升序
return;//此时返回结果
}
}
}
}
//如果循环结束都没有找到第一个升序的，说明是全逆序，此时的结果应该是把你直接变成升序
sort(nums.begin(),nums.end());
}
};九、排列序列
class Solution {
public:
string getPermutation(int n, int k)
{
vector<int> factorial(n);//用来统计各个阶乘
factorial[0]=1;
for(int i=1;i<n;++i)//统计1——（n-1）！的阶乘
{
factorial[i]= factorial[i-1]*i;
}
--k;//康托展开
vector<int> check(n+1,1);//可选数
string ret;
ret.reserve(n);
for(int i=1;i<=n;++i)
{
int order=k/factorial[n-i]+1;//确定了康拖的首位
for(int j=1;j<=n;++j)//告诉check数组，该位置得是0 不能再选
{
order-=check[j];
if(order==0)
{
ret.push_back(j+'0');
check[j]=0;//说明此数被选过
break;
}
}
k%=factorial[n-i];//去找下一个数
}
return ret;
}
};排列和子集问题就总结到这啦！！回溯有关的题关键就是画树状图，然后根据树状图去思考怎么进行深搜、回溯和剪枝！！
