当前位置：首页 > news >正文

《算法题讲解指南：递归，搜索与回溯算法--穷举vs深搜vs回溯vs剪枝》--12.全排列，13.子集

news 2026/6/4 15:46:18

🔥小叶-duck：个人主页

❄️个人专栏：《Data-Structure-Learning》《C++入门到进阶&自我学习过程记录》
《算法题讲解指南》--优选算法
《算法题讲解指南》--递归、搜索与回溯算法
《算法题讲解指南》--动态规划算法

✨未择之路，不须回头
已择之路，纵是荆棘遍野，亦作花海遨游

什么是回溯算法？

回溯算法的模板(不要死记硬背)

回溯算法的应用

12.全排列

题目链接：

题目描述：

题目示例：

解法：

算法思路：

C++算法代码：

算法总结及流程解析：

13.子集

题目链接：

题目描述：

题目示例：

解法:

算法思路:

C++算法代码(解法一：决策树->当前位置选和不选)：

C++算法代码(解法二：决策树->i层的子集包含i个元素)：

算法总结及流程解析：

结束语

什么是回溯算法？

回溯算法是一种经典的递归算法，通常用于解决组合问题、排列问题和搜索问题等。
回溯算法的基本思想：从一个初始状态开始，按照一定的规则向前搜索，当搜索到某个状态无法前进时，回退到前一个状态，再按照其他的规则搜索。回溯算法在搜索过程中维护一个状态树，通过遍历状态树来实现对所有可能解的搜索。
回溯算法的核心思想：“试错”，即在搜索过程中不断地做出选择，如果选择正确，则继续向前搜索；否则，回退到上一个状态，重新做出选择。回溯算法通常用于解决具有多个解，且每个解都需要搜索才能找到的问题。

回溯算法的模板(不要死记硬背)

void backtrack(vector<int>& path, vector<int>& choice, ...) { // 满足结束条件 if (/* 满足结束条件 */) { // 将路径添加到结果集中 res.push_back(path); return; } // 遍历所有选择 for (int i = 0; i < choices.size(); i++) { // 做出选择 path.push_back(choices[i]); // 做出当前选择后继续搜索 backtrack(path, choices); // 撤销选择 path.pop_back(); } }

其中， path 表示当前已经做出的选择， choices 表示当前可以做的选择。在回溯算法中，我们需要做出选择，然后递归地调用回溯函数。如果满足结束条件，则将当前路径添加到结果集中；否则，我们需要撤销选择，回到上一个状态，然后继续搜索其他的选择。
回溯算法的时间复杂度通常较高，因为它需要遍历所有可能的解。但是，回溯算法的空间复杂度较低，因为它只需要维护一个状态树。在实际应用中，回溯算法通常需要通过剪枝等方法进行优化，以减少搜索的次数，从而提高算法的效率。

回溯算法的应用

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

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

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

1 [1,2]
2 [2,1]
3 [1,3]
4 [3,1]
5 [2,3]
6 [3,2]

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

1 []
2 [1]
3 [2]
4 [3]
5 [1,2]
6 [1,3]
7 [2,3]
8 [1,2,3]

总结
回溯算法是一种非常重要的算法，可以解决许多组合问题、排列问题和搜索问题等。回溯算法的核心思想是搜索状态树，通过遍历状态树来实现对所有可能解的搜索。回溯算法的模板非常简单，但是实现起来需要注意一些细节，比如如何做出选择、如何撤销选择等。

12.全排列

题目链接：

46. 全排列 - 力扣（LeetCode）

题目描述：

题目示例：

解法：

算法思路：

典型的回溯题目，我们需要在每一个位置上考虑所有的可能情况并且不能出现重复。通过深度优先搜索的方式，不断地枚举每个数在当前位置的可能性，并回溯到上一个状态，直到枚举完所有可能性，得到正确的结果。
每个数是否可以放入当前位置，只需要判断这个数在之前是否出现即可。具体地，在这道题目中，我们可以通过一个递归函数 backtrack和标记数组visited 来实现全排列。=

递归函数设计：

void backtrack(vector<vector<int>>& res,vector<int>& nums,vector<bool>& visited,vector<int>& ans, int step, int len)

参数：step(当前需要填入的位置)，len (数组长度)；
返回值：无;
函数作用：查找所有合理的排列并存储在答案列表中。

递归流程如下：
1.首先定义一个二维数组res用来存放所有可能的排列，一个一维数组ans用来存放每个状态的排列，一个一维数组visited 标记元素，然后从第一个位置开始进行递归;
2.在每个递归的状态中，我们维护一个步数step，表示当前已经处理了几个数字;
3.递归结束条件：当 step 等于 nums数组的长度时，说明我们已经处理完了所有数字，将当前数组存入结果中;
4.在每个递归状态中，枚举所有下标i，若这个下标未被标记，则使用nums数组中当前下标的元素:
a.将visited[i]标记为 1;
b.ans 数组中第 step个元素被nums[i]覆盖;
c.对第step+1个位置进行递归;
d.将visited[i]重新赋值为0，表示回溯;
5.最后，返回 res。
特别地，我们可以不使用标记数组，直接遍历 step 之后的元素(未被使用)，然后将其与需要递归的位置进行交换即可。

C++算法代码：

class Solution { public: vector<vector<int>> ret; bool check[7]; vector<int> path; 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; } } } };

算法总结及流程解析：

13.子集

题目链接：

78. 子集 - 力扣（LeetCode）

题目描述：

题目示例：

解法:

算法思路:

为了获得nums数组的所有子集，我们需要对数组中的每个元素进行选择或不选择的操作，即nums数组一定存在2^(数组长度)个子集。对于查找子集，具体可以定义一个数组，来记录当前的状态，并对其进行递归。
对于每个元素有两种选择:1.不进行任何操作;2.将其添加至当前状态的集合。在递归时我们需要保证递归结束时当前的状态与进行递归操作前的状态不变，而当我们在选择进行步骤2进行递归时，当前状态会发生变化，因此我们需要在递归结束时撤回添加操作，即进行回溯。

递归函数设计：

void backtrack(vector<vector<int>>& res,vector<int>& nums,vector<bool>& visited,vector<int>& ans, int step, int len)

参数：step(当前需要填入的位置)，len (数组长度)；
返回值：无;
函数作用：查找所有合理的排列并存储在答案列表中。

递归流程如下:
1.递归结束条件:如果当前需要处理的元素下标越界，则记录当前状态并直接返回;
2.在递归过程中，对于每个元素，我们有两种选择：
不选择当前元素，直接递归到下一个元素;
选择当前元素，将其添加到数组末尾后递归到下一个元素，然后在递归结束时撤回添加操作;
3.所有符合条件的状态都被记录下来，返回即可。

C++算法代码(解法一：决策树->当前位置选和不选)：

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; } //选择1：不选当前值 dfs(nums, i + 1); //选择2：选择当前值 path.push_back(nums[i]); dfs(nums, i + 1); //回溯->恢复现场 path.pop_back(); } };

C++算法代码(解法二：决策树->i层的子集包含i个元素)：

class Solution { public: vector<vector<int>> ret; vector<int> path; vector<vector<int>> subsets(vector<int>& nums) { dfs(nums, 0); return ret; } //解法二：决策树->i层的子集包含i个元素 void dfs(vector<int>& nums, int index) { ret.push_back(path); for(int i = index; i < nums.size(); i++) { path.push_back(nums[i]); dfs(nums, i + 1); //回溯->恢复现场 path.pop_back(); } } };