目录
- 不管什么深搜、回溯还是剪枝，画出决策树就好啦
- 回溯就是完成递归过程中公用状态的还原
1.全排列
链接：46. 全排列
给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。
示例 1：
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]示例 2：
输入：nums = [0,1]
输出：[[0,1],[1,0]]示例 3：
输入：nums = [1]
输出：[[1]]题解
- 其实这道题本身是一个穷举(枚举)的题，3个数你可以三层for循环，但是如果10个数，100个数呢？
- 对于数多的显然不合适！此时我们就需要借助递归把所有情况都枚举出来。
解决回溯的步骤：
画出决策树，越详细越好！
设计代码
- 全局变量
- dfs函数
- 细节问题
1.画出决策树
- 就是在暴力枚举这道题过程中如何不重不漏的把所有情况枚举到
- 就是把自己的想法按照树的样子画下来。
第一次选择可以直接选123中任何一个，接下来每次选择都是从123中选。
- 但是此时你会发现比如第一次选1，下一次还选1就会有重复的情况，因此这个1我们是要把它剪掉的，不考虑有1的情况。
- 第二次选择假设选择的是2，在往下选择就还是有123，但是此时剪掉的应该更多，12不能选，只能选3，所有最终这条分支就是123，同理其他也是这样选出。
- 决策树画的越详细越好，就是把每一步都画出来，这样你就会发现每一个节点干的事情都是一样的，都是枚举整个数组。
- 无非就是一些分支被我们剪掉。
- 当一直在干同一件事情的时候我们决策树就画成功了，因为可以改成递归的代码。
2.设计代码
1.全局变量
- 全局变量就看这个递归需要什么东西和以及最终要返回什么东西。
- 全局变量的使用仁者见仁智者见智，也可以把全局变量换成参数在递归函数中传递。
- 看个人选择，不过还是建议使用全局变量！
首先来递归要返回的二维数组，再来一个把每次选择都要记录的path。
- 当path.size() == nums.size() 说明已经找到一个符合的组合
- 此时把path放到ret里，然后回溯 ，注意要 恢复现场。
- 在说这个之前我们要说一说这个剪枝的事情。
剪枝怎么解决？就是如果避免下一次选择重复的数字。
此时我们也需要一个数组，用一个bool 类型的数组。
- 来判断一下该条路径下的数是否已经被使用过了。
- bool数组中记录nums数组中的数字是否已经被使用过。
check[0] 对应 1， check[1] 对应 2 ， check[2] 对应3，check初始化都为false
只有对应数字被使用了 check[i]=true，说明这个数字已经被使用过了，下一次就不要选这个数字了。
2.dfs函数
- 仅需关心，某一个节点在干什么事情。
3.细节问题
- 回溯
当我要回去的时候，需要把这个3干掉，就是向上回去把path最后一个元素干掉
但是别忘记了check也是一个全局的， 你用3的时候会把check对应位置置为true，那你向上返回这个3你都不用了，是不是要把3复原 呀。
- 干掉 path 最后一个元素
- 修改 check 数组
剪枝
- 这里前面说过。
递归出口
- 遇到叶子节点的时候，直接添加结果。不用在到空了。
- 这样的题一定是决策树画出来是最重要的，第二步设计代码你想到哪一点写那一点都可以。
class Solution {
vector<vector<int>> ret;
bool check[7]={false};
vector<int> path;
public:
vector<vector<int>> permute(vector<int>& nums)
{
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++)
{
if(check[i]==false) //剪枝
{
path.push_back(nums[i]);
check[i]=true;//借助 全局变量标记
dfs(nums); //决策树 深度遍历
path.pop_back();//尾删
check[i]=false;
}
}
}
};2.子集
链接：78. 子集
给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。
解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。
示例 1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]题解
这里我们采用两种策略来解决这个问题，虽然是两种策略，但都是深搜，所以我们的思考方式是一样的。
解法一：
- 画出决策树
- 设计代码
- 全局变量
- dfs
- 细节：回溯、剪枝、递归出口
首先画决策树，我们想想如何能够把所有子集不重不漏全部枚举出来。
- 我们从子集定义出发，子集是这个数组里面选or不选某些数形成新的集合就是它的子集。
- 因此我们就单独盯着数组中每个数字考虑选or不选来画出我们的决策树。
此时所有叶子节点就是数组所有不重复的子集。
- 现在我们仅需把这颗决策树转换成代码就可以了。
- 之前的题无非就是直接把树画好给我们了，现在是要我们自己画一颗树。
既然叶子节点是我们的结果，因此我们需要两个全局变量
- 一个二维数组ret，一个一维数组path
- path把每次选or不选路径记录下来，然后ret把path记录下来。
这道题我们并不需要剪枝。
dfs函数我们就盯着某一个位置在干什么。
- 比如绿圈的位置，因为上面已经选过了，所以要需要考虑这一次的数选or不选，所以dfs不仅要这个nums，还要告诉我你当前选到了那个位置，dfs(nums，pos)
- 选就加入到path里，然后dfs(nums，pos+1)下一层
- 不选直接 dfs(nums，pos+1)下一层
细节问题：
- 回溯要恢复现场，因此我们在选的这条路径在递归返回之后把path最后一个位置pop掉，剪枝我们这里没有。
- 递归出口当pos==nums.size()的时候，把path放到ret里，然后返回即可。
重点关注 ：如何对子集实现选不选的功能
//选
path.push_back(nums[pos]);
dfs(nums,pos+1);
path.pop_back(); // 恢复现场
// 不选
dfs(nums,pos+1);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 pos)
{
if(pos==nums.size())
{
ret.emplace_back(path);//减少拷贝
return;
}
//选择
path.push_back(nums[pos]);
//下一个
dfs(nums,pos+1);
//不选择
path.pop_back();//回溯
//下一个
dfs(nums,pos+1);
}
};解法二：
也是上面一样的步骤
- 画出决策树
- 设计代码
- 全局变量
- dfs
- 细节：回溯、剪枝、递归出口
这里我们换一种思考方式，当我们选的子集是没有元素、只有一个元素、只有两个元素、只有三个元素等等。
- 前面的是盯着某一个数选or不选
- 现在我们直接看看最终要的子集要么没有，要么一个元素，要么两个元素，要么三个元素等等，从小到大去选。
- 并且每次是从这个被选的数的后面再次选。
并且每一个节点都是我们想要的结果。
你会发现我们这种解法比上面少了很多没有必要的情况。
全局变量还是上面那两个，dfs函数 从当前节点位置开始向后枚举，所以也要知道当前位置 dfs(nums，pos)。
- for(int i=pos;i<nums.size();++i) 把路径上的节点放入path
- 然后递归到下一层dfs(nums，pos+1)，当递归返回收把path最后一个位置pop掉。
- 回溯也要恢复现场，把path最后一个位置pop掉，这里我们不用剪枝
- 递归出口，每次进入递归函数后先把path先放到ret里。
- 然后也不需要出口，循环条件不满足就出去了。
class Solution {
vector<vector<int>> ret;
vector<int> path;
public:
vector<vector<int>> subsets(vector<int>& nums) {
dfs(nums,0);
return ret;
}
void dfs(vector<int>& nums,int pos)
{
ret.push_back(path);
for(int i=pos;i<nums.size();++i)
{
path.push_back(nums[i]);
dfs(nums,i+1);
path.pop_back(); // 恢复现场
}
}
};为什么上面这个回溯不用return？
- 通过 for size 来控制的回溯，到 size 就 return 了