全排列

题目链接

题解

1. 画一颗决策树
2. 全局变量：
int[ ][ ] ret：用于存结果的二维数组
int[ ] path：用于存每次路径的答案
bool[ ] check：判断这个数是否已经用过，用于剪枝，剪掉重复的，比如不可能出现1 1 2，就把第二个1剪掉了
3. 设计dfs函数：只需要关心某个节点在干什么即可，其实这题关心某一条路径就可以写出dfs函数
4. 回溯：
1、把path的最后一个元素干掉
2、把最后这个元素的bool改为false（修改check数组）
剪枝：
1、bool[ ] check：一直在做剪枝，保证数字不重复
递归出口：
1、到达叶子节点的path的长度和nums中一个元素的长度相同（遇到叶子节点的时候直接添加结果）

代码

class Solution 
{
public:bool check[7]; // 检查是否可以剪枝vector<vector<int>> ret; // 记录每次的路径vector<int> path; // 路径vector<vector<int>> permute(vector<int>& nums) {dfs(nums);return ret;}// dfs只需要关心每一条路径在干什么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;}}}
};

子集

题目链接

题解

1. 决策树的画法是：选还是不选
2. 全局变量：path记录每次的路径，ret记录所有路径3
3. dfs：函数头需要nums和i参数，i参数记录每次选的位置，总共3个位置
选：path += nums[i]，dfs去下一层，然后再恢复现场
不选：dfs直接去下一层
4. 细节处理：
剪枝：没有剪枝
回溯：选的时候需要恢复现场
递归出口：i == nums.size()，到叶子节点的下一层之后，把路径给ret，再返回

1. 决策树的画法：第一层是0个，第二层是1个，第三层是2个，第四层是3个，以此类推
2. 全局变量：path记录路径，ret记录所有路径的结果
3. dfs：函数头需要参数nums和pos，pos用于标记哪个位置是否已经使用过了
4. 进入dfs函数后就应该把路径加入到ret中，第一次是空路径，每次进来都是一个路径
5. 细节处理：
回溯：每次dfs完进行回溯
剪枝：不需要进行剪枝，for已经处理好了，i = pos就记录了上次的pos位置
递归出口：不需要递归出口，函数结束了就是递归出口

代码

class Solution 
{
public:// 解法一:vector<vector<int>> ret;vector<int> path; vector<vector<int>> subsets(vector<int>& nums) {dfs(nums,0);return ret;} void dfs(vector<int> nums,int i){if(i == nums.size()){ret.push_back(path);return;}// 怎么区分选或者是不选->下面// 不选dfs(nums,i+1);          // 选path.push_back(nums[i]);dfs(nums,i+1);// 回溯->恢复现场path.pop_back();}
};class Solution 
{
public:// 解法二:vector<vector<int>> ret;vector<int> path; vector<vector<int>> subsets(vector<int>& nums) {dfs(nums,0);return ret;} void dfs(vector<int> nums,int i){ret.push_back(path);for(int j = i;j < nums.size();j++){path.push_back(nums[j]);dfs(nums,j+1);path.pop_back();// 恢复现场}}
};

总结

dfs就分为五步：
1. 画决策树：只要正确画出决策树就能写出正确的代码
2. 全局变量：写出ret记录所有路径，path记录每次的路径，check标记是否使用过该位置
3. dfs：函数头，根据决策树考虑使用几个参数，只关心某个节点在干什么的情况或者是某一条路径的情况
4. dfs的函数体：根据决策树设计分析函数题如何写
5. 细节处理：回溯->恢复现场，剪枝->把不要的情况剪掉，递归出口->一般是根据叶子节点的情况得到的，比如 i == nums.size()，i走到数组的最后一个位置的下一个位置并且把路径加入到ret中就返回