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

一、排列问题

全排列II

题目链接

题解

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

代码

1. class Solution
2. {
3. public:
4.     vector<vector<int>> ret;
5.     vector<int> path;
6.     bool check[9];
7.     vector<vector<int>> permuteUnique(vector<int>& nums)
8.     {
9.         sort(nums.begin(),nums.end());
10.         dfs(nums);
11.         return ret;
12.     }
14.     void dfs(vector<int> nums)
15.     {
16.         if(path.size() == nums.size())
17.         {
18.             ret.push_back(path);
19.             return;
20.         }
22.         // 如何把重复的数字剪掉
23.         for(int i = 0;i < nums.size();i++)
24.         {
25.             // 合法的剪枝,不合法就不进行dfs
26.             // if((check[i] == false)&&
27.             // (i == 0||nums[i] != nums[i-1]||check[i-1] == true))
28.             // {
29.             //     check[i] = true;
30.             //     path.push_back(nums[i]);
31.             //     dfs(nums);
32.             //     // 恢复现场
33.             //     check[i] = false;
34.             //     path.pop_back();
35.             // }
37.             // 考虑不合法的剪枝,跳过不合法的剪枝
38.             if((check[i] == true)||
39.             (i != 0&&nums[i] == nums[i-1]&&check[i-1] == false))
40.             continue;
41.         
42.                 check[i] = true;
43.                 path.push_back(nums[i]);
44.                 dfs(nums);
45.                 // 恢复现场
46.                 check[i] = false;
47.                 path.pop_back();
48.         }
49.     }
50. };

复制代码

优美的排列

题目链接

题解

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

代码

1. class Solution
2. {
3. public:
4.     int n;
5.     int ret;
6.     bool check[16];
7.     vector<int> path;
8.     int countArrangement(int _n)
9.     {
10.         n = _n;
11.         dfs(1);
12.         return ret;
13.     }
15.     void dfs(int pos)
16.     {
17.         if(path.size() == n)
18.         {
19.             ret++;
20.             return;
21.         }
23.         for(int i = 1;i <= n;i++)
24.         {
25.             if(pos % i == 0 || i % pos == 0)
26.             {
27.                 if(check[i] == false)
28.                 {
29.                     check[i] = true;
30.                     path.push_back(i);
31.                     dfs(pos+1);
32.                     // 恢复现场
33.                     path.pop_back();
34.                     check[i] = false;
35.                 }
36.             }
37.         }
38.     }
39. };

复制代码

二、子集问题

字母大小写全排列

题目链接

题解

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

代码

1. class Solution
2. {
3. public:
4.     vector<string> ret;
5.     string path;
6.     vector<string> letterCasePermutation(string s)
7.     {
8.         dfs(s,0);
9.         return ret;
10.     }
12.     void dfs(string s,int pos)
13.     {
14.         // 为什么不能写pos == s.size()
15.         if(pos == s.size())
16.         {
17.             ret.push_back(path);
18.             return;
19.         }
20.         
21.         char ch = s[pos];
22.         // 不变
23.         path.push_back(ch);
24.         dfs(s,pos+1);
25.         path.pop_back();
27.         // 变
28.         if(ch < '0' || ch > '9')
29.         {
30.             ch = change(ch);
31.             path.push_back(ch);
32.             dfs(s,pos+1);
33.             path.pop_back();
34.         }
35.     }
36.     char change(char ch)
37.     {
38.         if(ch >= 'a' && ch <= 'z') ch -= 32;
39.         else ch += 32;
40.         return ch;
41.     }
42. };

复制代码

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

题目链接

题解

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

代码

1. class Solution
2. {
3. public:
4.     long long sum = 0;// 记录全部路径的异或和
5.     long long path = 0;// 记录一条路径的异或和
6.     int subsetXORSum(vector<int>& nums)
7.     {
8.         dfs(nums,0);
9.         return sum;
10.     }
12.     void dfs(vector<int> nums,int pos)
13.     {
14.         sum += path;
15.         for(int i = pos;i < nums.size();i++)
16.         {
17.             path ^= nums[i];
18.             dfs(nums,i+1);
19.             path ^= nums[i];
20.             // 不能使用pos代替i,如果进行回溯回来,
21.             // 进行循环,path始终异或nums[pos]
22.         }
23.     }
24. };

复制代码

三、组合问题

电话号码的字母组合

题目链接

题解

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

代码

1. class Solution
2. {
3. public:
4.     vector<string> ret;
5.     string path;
6.     string hash[10] = {"","","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
7.     vector<string> letterCombinations(string digits)
8.     {
9.         if(digits.size() == 0) return ret;
10.         dfs(digits,0);   
11.         return ret;
12.     }
14.     void dfs(string digits,int pos)
15.     {
16.         if(pos == digits.size())
17.         {
18.             ret.push_back(path);
19.             return;
20.         }
22.         for(int i = 0;i < hash[digits[pos] - '0'].size();i++)
23.         {
24.             path.push_back(hash[digits[pos] - '0'][i]);
25.             dfs(digits,pos+1);
26.             // 恢复现场
27.             path.pop_back();
28.         }
29.     }
30. };

复制代码

括号天生

题目链接

题解

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

代码

1. class Solution
2. {
3. public:
4.     vector<string> ret;
5.     string path;
6.     int left,right;
7.     vector<string> generateParenthesis(int n)
8.     {
9.         dfs(n);
10.         return ret;
11.     }
12.    
13.     void dfs(int n)
14.     {
15.         if(right == n)
16.         {
17.             ret.push_back(path);
18.             return ;
19.         }
21.         if(left < n)
22.         {
23.             path.push_back('(');
24.             left++;
25.             dfs(n);
26.             path.pop_back();
27.             left--;
28.         }
29.         if(left > right)
30.         {
31.             path.push_back(')');
32.             right++;
33.             dfs(n);
34.             path.pop_back();
35.             right--;
36.         }
38.     }
39. };

复制代码

组合

题目链接

题解

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

代码

1. class Solution
2. {
3. public:
4.     vector<vector<int>> ret;
5.     vector<int> path;
6.     int k;
7.     vector<vector<int>> combine(int n, int _k)
8.     {
9.         k = _k;
10.         dfs(n,1);
11.         return ret;
12.     }
14.     void dfs(int n,int pos)
15.     {
16.         if(path.size() == k)
17.         {
18.             ret.push_back(path);
19.             return ;
20.         }
22.         for(int i = pos;i <= n;i++)
23.         {
24.             path.push_back(i);
25.             dfs(n,i+1);
26.             path.pop_back();// 恢复现场
27.         }
28.     }
29. };

复制代码

目的和

题目链接

题解

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

代码

1. class Solution
2. {
3. public:
4.     int ret,target;
5.     int findTargetSumWays(vector<int>& nums, int _target)
6.     {
7.         target = _target;
8.         dfs(nums,0,0);
9.         return ret;
10.     }
12.     void dfs(vector<int>& nums,int pos,int path)
13.     {
14.         if(pos == nums.size())
15.         {
16.             if(target == path)
17.             ret++;
18.             return;
19.         }
21.         // 加法,放在参数中函数帮我们自动恢复现场了
22.         dfs(nums,pos+1,path + nums[pos]);
24.         // 减法
25.         dfs(nums,pos+1, path - nums[pos]);
26.     }
27. };

复制代码

组合总和

题目链接

题解

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

代码

1. class Solution
2. {
3. public:
4.     vector<vector<int>> ret;
5.     vector<int> path;
6.     int target;
7.     vector<vector<int>> combinationSum(vector<int>& candidates, int _target)
8.     {
9.         target = _target;
10.         dfs(candidates,0,0);
11.         return ret;
12.     }
14.     void dfs(vector<int> candidates,int pos,int sum)
15.     {
16.         if(sum == target)
17.         {
18.             ret.push_back(path);
19.             return;
20.         }
21.         // 枚举完了所有的位置也不是target,这个总和比较小
22.         if(pos == candidates.size()) return;
24.         for(int i = pos;i < candidates.size();i++)
25.         {
26.             if(sum > target) continue;
27.             
28.             path.push_back(candidates[i]);
29.             dfs(candidates,i,sum + candidates[i]);
30.             path.pop_back();
31.         }
32.     }
33. };

复制代码

解法二：罗列每个数的数目
1. 和解法一不一样的地方就是dfs函数的实现不一样

1. class Solution
2. {
3. public:
4.     vector<vector<int>> ret;
5.     vector<int> path;
6.     int target;
7.     vector<vector<int>> combinationSum(vector<int>& candidates, int _target)
8.     {
9.         target = _target;
10.         dfs(candidates,0,0);
11.         return ret;
12.     }
14.     void dfs(vector<int> candidates,int pos,int sum)
15.     {
16.         if(sum == target)
17.         {
18.             ret.push_back(path);
19.             return;
20.         }
21.         // 枚举完了所有的位置也不是target,这个总和比较小
22.         if(pos == candidates.size() || sum > target) return;
23.          
24.         // 枚举个数
25.         for(int k = 0;sum + k * candidates[pos] <= target;k++)
26.         {
27.             if(k) path.push_back(candidates[pos]);
28.             dfs(candidates,pos+1,sum + k*candidates[pos]);
29.         }
30.         
31.         // 整块恢复现场
32.         for(int k = 1;sum + k * candidates[pos] <= target;k++)
33.         {
34.             path.pop_back();
35.         }
36.     }
37. };

复制代码

总结

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

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。