DFS：深搜+回溯+剪枝解决排列、子集问题

创作不易，感谢三连支持！！

一、全排列I

. - 力扣（LeetCode）

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

. - 力扣（LeetCode）

方案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：考虑合法的才进dfsfor(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：考虑合法的才进dfsfor(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;}}}
};

三、优美的排列

. - 力扣（LeetCode）

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

. - 力扣（LeetCode）

策略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

. - 力扣（LeetCode）

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();}}
};

六、找出所有子集的异或总和再求和

. - 力扣（LeetCode）

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];//利用消消乐的性质恢复现场}}
};

七、字母大小写全排列

. - 力扣（LeetCode）

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);}
};

八、下一个排列

. - 力扣（LeetCode）

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());}
};

九、排列序列

. - 力扣（LeetCode）

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;}
};

排列和子集问题就总结到这啦！！回溯有关的题关键就是画树状图，然后根据树状图去思考怎么进行深搜、回溯和剪枝！！