文章目录
- 全排列
- 题解
- 代码
- 子集
- 题解
- 代码
- 总结
全排列
题目链接
题解
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中就返回