dfs刷题排列问题 + 子集问题 + 组和问题总结

一、排列问题

全排列II

题目链接

题解

1. 这题和全排列那题框架是一样的，就是剪枝操作不一样
2. 同一节点出现相同元素肯定会重复，所以把同一节点的相同元素剪掉
3. 同一个数只能出现一次，用check数组剪枝
分为两种情况进行剪枝：
1、只关心不合法的分支：
不合法的进行跳过（剪枝）
check[i] == true || ( i != 0 &&nums[i] == nums[i-1] && check[i-1] == false)
这个点是已经使用过的，或者是这个点和前一个点是相同的并且前一个点没有使用过，i != 0保证不越界
2、只关心合法的分支：
合法的分支才进行dfs
check[i] == false && (i == 0 || nums[i] != nums[i-1] || check[i] == true)
这个点没有被使用过并且该点为第一个点肯定可以进行dfs，或者是该点和前一个点不相同也可以dfs，或者是该点和前一个点相同，但是前一个点上一层已经使用过了，这个点这层可以继续使用，因为它们是用的不同位置

代码

class Solution 
{
public:vector<vector<int>> ret;vector<int> path;bool check[9];vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(),nums.end());dfs(nums);return ret;}void dfs(vector<int> nums){if(path.size() == nums.size()){ret.push_back(path);return;}// 如何把重复的数字剪掉for(int i = 0;i < nums.size();i++){// 合法的剪枝,不合法就不进行dfs// if((check[i] == false)&&// (i == 0||nums[i] != nums[i-1]||check[i-1] == true))// {//     check[i] = true;//     path.push_back(nums[i]);//     dfs(nums);//     // 恢复现场//     check[i] = false;//     path.pop_back();// }// 考虑不合法的剪枝,跳过不合法的剪枝if((check[i] == true)||(i != 0&&nums[i] == nums[i-1]&&check[i-1] == false))continue;check[i] = true;path.push_back(nums[i]);dfs(nums);// 恢复现场check[i] = false;path.pop_back();}}
};

优美的排列

题目链接

题解

1. 画出决策树
2. 全局变量的设计：ret用来记录优美排列的个数，check数组检查是否可以剪枝，n设计成全局变量就不需要进行传参了
3. 剪枝：第一种剪枝不能出现重复的数，第二种剪枝不满足整除条件的
4. 回溯：如图我们每个位置都要进行判断，每个位置都会走一遍，递归完后进行恢复现场，把最后一位pop_back
5. 递归出口：当path路径的长度等于n时为递归出口
6. for循环的i = 1开始是因为要遍历所有的路径，dfs中pos+1是因为此位置遍历完会来到下一个位置进行遍历，画出决策树就很清晰了

代码

class Solution
{
public:int n;int ret;bool check[16];vector<int> path;int countArrangement(int _n) {n = _n;dfs(1);return ret;}void dfs(int pos){if(path.size() == n){ret++;return;}for(int i = 1;i <= n;i++){if(pos % i == 0 || i % pos == 0){if(check[i] == false){check[i] = true;path.push_back(i);dfs(pos+1);// 恢复现场path.pop_back();check[i] = false;}} }}
};

二、子集问题

字母大小写全排列

题目链接

题解

1. 画出决策树
2. 全局变量：ret记录最终的结果，path记录每次的路径
3. 剪枝：没有剪枝
4. 回溯：到达叶子节点的时候记录完进行回溯，pop_back最后一个位置的数来到上一层
5. 递归出口：pos位置为n时，是最后一个数据的下一个位置，为递归出口
6. 这题和选和不选基本上是一样的，子集问题，pos这个位置变或者不变然后来到下一个位置，所以dfs(pos+1)，变的情况为小写字母时转为大写字母，大写转为小写，不变就直接push

代码

class Solution 
{
public:vector<string> ret;string path;vector<string> letterCasePermutation(string s) {dfs(s,0);return ret;}void dfs(string s,int pos){// 为什么不能写pos == s.size()if(pos == s.size()){ret.push_back(path);return;}char ch = s[pos];// 不变path.push_back(ch);dfs(s,pos+1);path.pop_back();// 变if(ch < '0' || ch > '9'){ch = change(ch);path.push_back(ch);dfs(s,pos+1);path.pop_back();}}char change(char ch){if(ch >= 'a' && ch <= 'z') ch -= 32;else ch += 32;return ch;}
};

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

题目链接

题解

1. 画出决策树
2. 全局变量：用sum记录最终的结果，用path记录一个集合的异或和
3. 剪枝：没有剪枝
4. 回溯：每次异或当前元素就抵消掉这个元素了，然后回到上一层
5. 递归出口：没有递归出口，每次把path加到sum中即可
6. for循环中每次从pos位置开始向后枚举，避免重复，dfs(i+1)，i+1就是数组中下一个位置的数，相当于剪枝了

代码

class Solution 
{
public:long long sum = 0;// 记录全部路径的异或和long long path = 0;// 记录一条路径的异或和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];// 不能使用pos代替i,如果进行回溯回来,// 进行循环,path始终异或nums[pos]}}
};

三、组合问题

电话号码的字母组合

题目链接

题解

1. 画出决策树
2. 全局变量：ret记录最终的结果，path记录每次的路径，哈希表记录下标的映射关系
3. 剪枝：没有剪枝
4. 回溯：到达叶子节点时，pop_back最后一个元素，恢复现场
5. 递归出口：path的长度和给定的数组的长度相同
6. for循环把所有的数都枚举出来了，所以i下标从0开始，dfs(pos+1)，每个位置枚举完跳到下一个位置继续枚举，这题主要是建立一个hash表记录每次的电话号码的数字对应的映射字符串

代码

class Solution 
{
public:vector<string> ret;string path;string hash[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};vector<string> letterCombinations(string digits) {if(digits.size() == 0) return ret;dfs(digits,0);   return ret;}void dfs(string digits,int pos){if(pos == digits.size()){ret.push_back(path);return;}for(int i = 0;i < hash[digits[pos] - '0'].size();i++){path.push_back(hash[digits[pos] - '0'][i]);dfs(digits,pos+1);// 恢复现场path.pop_back();}}
};

括号生成

题目链接

题解

1. 画出决策树
2. 全局变量：path记录每次的路径，ret记录最终的结果，left记录左括号的数量，right记录右括号的数量
3. 剪枝：第一种右括号的数量大于等于左括号的数量，第二中左括号的数量大于等于n的数量，开始的时候只能给左扩号，右括号剪枝，左右括号相等时，不能加入右括号，左括号大于n不符合结果，等于n时，再往下加就大于n，需要剪枝
4. 回溯：如果是左括号回溯，pop_back最后一个元素，left–，如果是右括号回溯，pop_back最后一个元素，right–
5. 递归出口：右括号的数量等于n时，为左右括号相等的最终结果

代码

class Solution 
{
public:vector<string> ret;string path;int left,right;vector<string> generateParenthesis(int n) {dfs(n);return ret;}void dfs(int n){if(right == n){ret.push_back(path);return ;}if(left < n){path.push_back('(');left++;dfs(n);path.pop_back();left--;}if(left > right){path.push_back(')');right++;dfs(n);path.pop_back();right--;}}
};

组合

题目链接

题解

1. 画出决策树
2. 全局变量：path记录每次的路径，ret记录最终的结果，k变为全局变量，不需要多传一个参数
3. 剪枝：不能重复出现相同的数剪枝，长度不够k也剪枝，这题可以从pos位置开始向后枚举，dfs(i+1)，i+1表示每次枚举当前数的下一个位置的数，相当于进行了剪枝
4. 回溯：到达叶子节点后，每次pop_back最后一个数
5. 递归出口：path的长度等于k的大小

代码

class Solution 
{
public:vector<vector<int>> ret;vector<int> path;int k;vector<vector<int>> combine(int n, int _k) {k = _k;dfs(n,1);return ret;}void dfs(int n,int pos){if(path.size() == k){ret.push_back(path);return ;}for(int i = pos;i <= n;i++){path.push_back(i);dfs(n,i+1);path.pop_back();// 恢复现场}}
};

目标和

题目链接

题解

1. 画出决策树
2. 全局变量：ret记录最终的结果，target变为全局变量就少传一个参数
3. 剪枝：没有剪枝
4. 回溯：函数自动回溯，将path作为参数，记录每条路径的大小，回到上一层，path变为了没有加减之前的path
5. 递归出口：最终的path等于target的大小，ret++
6. 这题就是每个数两种情况，要么加，要么减

代码

class Solution 
{
public:int ret,target;int findTargetSumWays(vector<int>& nums, int _target) {target = _target;dfs(nums,0,0);return ret;}void dfs(vector<int>& nums,int pos,int path){if(pos == nums.size()){if(target == path)ret++;return;}// 加法,放在参数中函数帮我们自动恢复现场了dfs(nums,pos+1,path + nums[pos]);// 减法dfs(nums,pos+1, path - nums[pos]);}
};

组合总和

题目链接

题解

解法一：每个pos位置填
1. 画出决策树
2. 全局变量：ret记录最终的结果，path记录每条路径，target变为全局变量就不需要传参target了
3. 剪枝：如果这条路径的和大于target剪枝，如果选择的路径重复了剪枝，这种可以使用i = pos位置开始向后枚举，dfs(i)，i表示每次从当前这个数向后枚举，不需要重复枚举这个数前面的数，就避免了重复的路径，达到了剪枝的效果
4. 回溯：sum在函数的参数中自动进行了回溯，pop_back最后一个元素，回到上一层
5. 递归出口：目标值等于记录的路径总和就找到一条路径，加入ret中，并返回给上一层

代码

class Solution 
{
public:vector<vector<int>> ret;vector<int> path;int target;vector<vector<int>> combinationSum(vector<int>& candidates, int _target) {target = _target;dfs(candidates,0,0);return ret;}void dfs(vector<int> candidates,int pos,int sum){if(sum == target){ret.push_back(path);return;}// 枚举完了所有的位置也不是target,这个总和比较小if(pos == candidates.size()) return;for(int i = pos;i < candidates.size();i++){if(sum > target) continue;path.push_back(candidates[i]);dfs(candidates,i,sum + candidates[i]);path.pop_back();}}
};

解法二：枚举每个数的数量
1. 和解法一不一样的地方就是dfs函数的实现不一样

class Solution 
{
public:vector<vector<int>> ret;vector<int> path;int target;vector<vector<int>> combinationSum(vector<int>& candidates, int _target) {target = _target;dfs(candidates,0,0);return ret;}void dfs(vector<int> candidates,int pos,int sum){if(sum == target){ret.push_back(path);return;}// 枚举完了所有的位置也不是target,这个总和比较小if(pos == candidates.size() || sum > target) return;// 枚举个数for(int k = 0;sum + k * candidates[pos] <= target;k++){if(k) path.push_back(candidates[pos]);dfs(candidates,pos+1,sum + k*candidates[pos]);}// 整块恢复现场for(int k = 1;sum + k * candidates[pos] <= target;k++){path.pop_back();}}
};

总结

1. 最重要的就是画出决策树
2. 全局变量：一般是path记录路径，ret记录各个路径的结果
3. 剪枝：看题目分析和看决策树
4. 回溯：一般是pop_back最后一个元素
5. 递归出口：看题目条件，或者是叶子节点