DFS：深搜+回溯+剪枝解决排列、子集问题
发布时间：2025-06-24 17:07:51 作者：北方职教升学中心 阅读量：940
创作不易，感谢三连支持！！
一、全排列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：考虑合法的才进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; } } }};三、优美的排列
. - 力扣（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; }};排列和子集问题就总结到这啦！！回溯有关的题关键就是画树状图，然后根据树状图去思考怎么进行深搜、回溯和剪枝！！
