【回溯+剪枝】回溯算法的概念 全排列问题

46. 全排列

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]]

提示：

• 1 <= nums.length <= 6
• -10 <= nums[i] <= 10
• nums 中的所有整数 互不相同

---

Ⅰ. 什么是回溯算法❓❓❓

​ 回溯算法是一种经典的递归算法，通常用于解决组合问题、排列问题和搜索问题等。

​ 回溯算法的基本思想：从一个初始状态开始，按照一定的规则向前搜索，当搜索到某个状态无法前进时，回退到前一个状态，再按照其他的规则搜索。回溯算法在搜索过程中维护一个状态树，通过遍历决策树来实现对所有可能解的搜索。

​ 回溯算法的核心思想：“试错”，即在搜索过程中不断地做出选择，如果选择正确，则继续向前搜索；否则，回退到上一个状态，重新做出选择。回溯算法通常用于解决具有多个解，且每个解都需要搜索才能找到的问题，也就是相当于是 枚举！

​ 其实说白了，回溯就是深搜，只不过回溯更加强调返回操作对一些题的理解是很重要的，所以专门给这种理解起了个回溯的专用词！其实回溯是有模板的，但是给出模板之后反而会限制思维，会想着怎么根据模板出发，而不是从题目本身出发，这是不行的，所以这里并不提供什么模板去背诵，当我们真正理解了回溯之后，其实写出来代码就会发现是和模板类似的！

Ⅱ. 回溯算法的应用

1、组合问题

​ 组合问题是指从给定的⼀组数（不重复）中选取出所有可能的 k 个数的组合。例如，给定数集 [1,2,3]，要求选取 k=2 个数的所有组合。其结果为：

[1, 2]
[1, 3]
[2, 3]

2、排列问题

​ 排列问题是指从给定的⼀组数（可重复）中选取出所有可能的 k 个数的排列。例如，给定数集 [1,2,3]，要求选取 k=2 个数的所有排列。其结果为：

[1,2]
[2,1]
[1,3]
[3,1]
[2,3]
[3,2]

3、子集问题

​ 子集问题是指从给定的一组数中选取出所有可能的子集，其中每个子集中的元素可以按照任意顺序排列。例如，给定数集 [1,2,3]，要求选取所有可能的子集。其结果为：

Ⅲ. 解题思路：回溯 + 剪枝

​ 首先根据题目要求，我们 需要两个全局变量 ret 和 path，ret 就是我们最后要返回的结果集，而 path 是存放当前正在走的全排列的元素！为什么要将它们设置为全局变量，而不是在函数中作为引用传递，其实是简化了函数需要填充的内容，并且在一定程度上也简化了我们的操作，尤其是后面一些题目比较说 N皇后的题目等等，如果用传引用的方式的话，其实是不太好控制的！虽说使用全局变量之后，在回溯的时候需要我们手动去恢复一下 path 的状态，但是这都是值得的！

​ 对于这类排列组合的问题，我们最好是能画出一棵详细一点的决策树（不要想的高大上，其实就是把情况枚举出来的树而已），这样子有利于帮助我们理解其中要注意的细节，如下面的图片所示！

​ 因为排列问题需要遍历所有的组合可能，包括顺序不同的组合可能，比如说 [1, 2] 和 [2, 1] 都需要满足，所以我们在排列问题中就不需要使用 index 来控制每次下一层也就是树枝之间的起始位置，只需要 每次都从数组下标为 0 开始遍历所有可能即可！

​ 但是这里还有一个问题，就是可能会出现重复调用了某个 nums[i]，比如说 [1, 2, 3] 中我们如果不对每个元素进行控制的话，可能会排列出 [1, 1, 1] 等情况，但是排列问题中我们 只能让每个元素都出现一次，所以需要使用一个 used 数组进行判断：

1. 将 used 数组初始化为 false。
2. 因为会出现重复的情况只在一条路径上，所以我们无需担心路径之间的重复，所以我们让 used[i] 为 false 表示是 nums[i] 还没走过，当我们在递归这条路径的下一个节点之前将 used[i] 变成 true，此时下一个节点层就会知道该 nums[i] 是走过的了，就不会再走了！然后回溯的时候将 used[i] 变成 false，这样子对同一树层是没有影响的，只会对下一层的路径产生影响！
3. 简单地说，当我们 判断到 used[i] == true，也就说明上一层已经将这个元素遍历过了，所以我们直接 continue 即可！

​ 说白了，上面的操作其实就是一个 剪枝 的操作！

​ 对于递归函数出口，我们只需要判断一下 path 数组的长度，是不是等于题目给的 nums 的长度，是的话说明当前序列已经是完成的了，则添加到 ret 结果集中然后直接返回即可！

​ 然后就是递归函数的主体，其实最重要的就是三步：

1. 处理当前层节点（处理）
2. 递归下一层节点（递归）
3. 进行回溯后的处理，防止影响后面的结果（回溯）

​ 可以结合下面的代码一起分析这个过程！

class Solution {
private:vector<vector<int>> ret; // 结果集vector<int> path;        // 存放当前正在走的全排列的元素vector<bool> used;       // 标记哪个元素已经走过了，用于剪枝操作，防止重复
public:vector<vector<int>> permute(vector<int>& nums) {used.resize(nums.size(), false);dfs(nums);return ret;}void dfs(vector<int>& nums){// 递归函数出口（将当前path添加到结果集中）if(path.size() == nums.size()){ret.push_back(path);return;}for(int i = 0; i < nums.size(); ++i) // 每次都是从0开始遍历，和组合问题不一样，排列问题需要遍历所有可能{// 进行剪枝操作，防止结果重复if(used[i] == true)continue;// 处理当前层节点path.push_back(nums[i]);used[i] = true;// 递归下一层节点dfs(nums);// 进行回溯后的处理，防止影响后面的结果path.pop_back();used[i] = false;}}
};