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++)
