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

算法妙妙屋-------1.递归的深邃回响：全排列的奇妙组合

news 来源：原创 2025/7/5 19:40:41

全排列的简要总结

全排列（Permutation）是数学中一个经典的问题，指的是从一组元素中，将所有元素按任意顺序排列形成的所有可能序列。

特点

输入条件：
- 给定一组互异的元素（通常为数组或字符串）。
- 例如：[1, 2, 3] 的全排列。
输出结果：
- 输出所有元素的排列组合。
- 例如：[1, 2, 3] 的全排列是：
```
[1, 2, 3]
[1, 3, 2]
[2, 1, 3]
[2, 3, 1]
[3, 1, 2]
[3, 2, 1]
```
数量公式：
- 对于 n 个互异元素，其全排列数量为 $n!$ （阶乘）。
- 例如：n = 3 时，全排列数量为 $3! = 6$ 。

实现方式

1. 递归法

通过递归交换或回溯实现：

#include <iostream>
#include <vector>
using namespace std;void backtrack(vector<int>& nums, int start, vector<vector<int>>& result) {if (start == nums.size()) {result.push_back(nums);return;}for (int i = start; i < nums.size(); i++) {swap(nums[start], nums[i]);           // 交换当前元素backtrack(nums, start + 1, result);  // 递归处理子问题swap(nums[start], nums[i]);           // 撤销交换（回溯）}
}int main() {vector<int> nums = {1, 2, 3};vector<vector<int>> result;backtrack(nums, 0, result);for (const auto& perm : result) {for (int num : perm) {cout << num << " ";}cout << endl;}return 0;
}

2. STL 函数

C++ 提供了 std::next_permutation，可以简单地生成字典序全排列：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;int main() {vector<int> nums = {1, 2, 3};do {for (int num : nums) {cout << num << " ";}cout << endl;} while (next_permutation(nums.begin(), nums.end()));  // 调用 STL 函数return 0;
}

应用场景

组合数学：
- 求解排列问题、旅行商问题等。
字符串操作：
- 对字符串生成不同排列，用于密码学、模式匹配等。
游戏与搜索：
- 如数独解法、八皇后问题等，依赖全排列进行搜索。
算法优化：
- 通过排列测试不同的输入顺序，寻找最优解。

优化与注意事项

剪枝优化：
- 在递归中排除不合法或重复的排列，提高效率。
重复元素：
- 如果输入包含重复元素，需要特殊处理以避免重复结果。
大规模问题：
- 对于规模较大的输入，因 $n!$ 增长较快，可能需要改用启发式算法。

全排列是基础的数学与算法问题，其思想在递归、动态规划和搜索算法中广泛应用！

1.全排列

题目链接：全排列
题目概述：
在这里插入图片描述
解题思路：递归流程如下：

⾸先定义⼀个⼆维数组res⽤来存放所有可能的排列，⼀个⼀维数组ans⽤来存放每个状态的排
列，⼀个⼀维数组visited标记元素，然后从第⼀个位置开始进⾏递归；
在每个递归的状态中，我们维护⼀个步数step，表⽰当前已经处理了⼏个数字；
递归结束条件：当step等于nums数组的⻓度时，说明我们已经处理完了所有数字，将当前数组
存⼊结果中；
在每个递归状态中，枚举所有下标i，若这个下标未被标记，则使⽤nums数组中当前下标的元
素：
a. 将visited[i]标记为1；
b. ans数组中第step个元素被nums[i]覆盖；
c. 对第step+1个位置进⾏递归；
d. 将visited[i]重新赋值为0，表⽰回溯；
最后，返回res。
• 特别地，我们可以不使⽤标记数组，直接遍历step之后的元素（未被使⽤），然后将其与需要递
归的位置进⾏交换即可。

class Solution {vector<vector<int>> it;vector<int> path;bool check[7];//check用来存储是否被使用过public:void dfs(vector<int>& nums, vector<int>& path) {if (path.size() == nums.size()) {it.push_back(path);}else {for (int a = 0; a < nums.size(); a++) {if (!check[a]) {path.push_back(nums[a]);check[a] = true;//标记，下次不能再选dfs(nums, path);check[a] = false;//回溯复原path.pop_back();}}}}vector<vector<int>> permute(vector<int>& nums) {dfs(nums, path);return it;}
};

2.子集

题目链接：子集
题目介绍：

在这里插入图片描述
解题思路：

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

class Solution {
public:vector<vector<int>> ret;vector<int> path;void dfs(vector<int>& nums, int pos) {if (pos == nums.size()) {ret.push_back(path);return;}// 选path.push_back(nums[pos]);dfs(nums, pos + 1);path.pop_back(); // 恢复现场// 不选dfs(nums, pos + 1);}vector<vector<int>> subsets(vector<int>& nums) {dfs(nums, 0);return ret;}
};

3.全排列||（！！！）

题目链接：全排列
题目介绍：
在这里插入图片描述
解题思路：
因此，我们需
要对相同元素定义⼀种规则，使得其组成的排列不会形成重复的情况：

我们可以将相同的元素按照排序后的下标顺序出现在排列中，通俗来讲，若元素s出现x次，则排序后的第2个元素s⼀定出现在第1个元素s后⾯，排序后的第3个元素s⼀定出现在第2个元素s后⾯，以此类推，此时的全排列⼀定不会出现重复结果。
例如：a1=1，a2=1，a3=2，排列结果为[1,1,2]的情况只有⼀次，即a1在a2前⾯，因为a2不会出现在a1前⾯从⽽避免了重复排列。
我们在每⼀个位置上考虑所有的可能情况并且不出现重复；
注意：若当前元素的前⼀个相同元素未出现在当前状态中，则当前元素也不能直接放⼊当前状态的数组，此做法可以保证相同元素的排列顺序与排序后的相同元素的顺序相同，即避免了重复排列出现。
通过深度优先搜索的⽅式，不断地枚举每个数在当前位置的可能性，并在递归结束时回溯到上⼀个状态，直到枚举完所有可能性，得到正确的结果。

class Solution {vector<int> path;vector<vector<int>> ret;bool check[9];public:vector<vector<int>> permuteUnique(vector<int>& nums) {sort(nums.begin(), nums.end());//先进行排序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 &&(i == 0 || nums[i] != nums[i - 1] || check[i - 1] != false))//非常的巧妙，想要插入必须满足以下要求   1.没有被插入过   2.第一位（没有前一项）||当前项和其前一项不一样||前一项已经被插入过了{path.push_back(nums[i]);check[i] = true;dfs(nums);path.pop_back(); // 恢复现场check[i] = false;}}}
};

4.括号生成（！！！）

题目链接：括号生成
题目介绍：在这里插入图片描述

解题思路：
从左往右进⾏递归，在每个位置判断放置左右括号的可能性，若此时放置左括号合理，则放置左括号
继续进⾏递归，右括号同理。
⼀种判断括号是否合法的⽅法：从左往右遍历，左括号的数量始终⼤于等于右括号的数量，并且左括
号的总数量与右括号的总数量相等。因此我们在递归时需要进⾏以下判断：

放⼊左括号时需判断此时左括号数量是否⼩于字符串总⻓度的⼀半（若左括号的数量⼤于等于字符
串⻓度的⼀半时继续放置左括号，则左括号的总数量⼀定⼤于右括号的总数量）；
放⼊右括号时需判断此时右括号数量是否⼩于左括号数量。

class Solution {
public:vector<string> str;void dfs(string it, int left,int right){if(left==0)//做括号全部用完{while(right){it.push_back(')');right--;}str.push_back(it);return;}it.push_back('(');//插入左括号dfs(it,left-1,right);it.pop_back();//回溯，回复现场if(right>left)//右括号剩余必须比左括号多{it.push_back(')');dfs(it,left,right-1);it.pop_back();//回溯}}vector<string> generateParenthesis(int n) {string it;int left=n;int right=n;it.push_back('(');//左边先插入一个（，避免第一个就是）的错误left--;dfs(it,left,right);return str;}
};

5.组合

题目链接：组合
题目介绍：
在这里插入图片描述
题⽬要求我们从1到n中选择k个数的所有组合，其中不考虑顺序。也就是说，[1,2]和[2,1]等价。我
们需要找出所有的组合，但不能重复计算相同元素的不同顺序的组合。对于选择组合，我们需要进⾏
如下流程：

所有元素分别作为⾸位元素进⾏处理；
在之后的位置上同理，选择所有元素分别作为当前位置元素进⾏处理；
为避免计算重复组合，规定选择之后位置的元素时必须⽐前⼀个元素⼤，这样就不会有重复的组合
（[1,2]和[2,1]中[2,1]不会出现）。

class Solution {
public:bool check[20];vector<vector<int>> it;vector<int> flag;void dfs(int n, int k, int first) {if (k) {for (int i = first; i <= n; i++) {flag.push_back(i);dfs(n, k-1,i+1);flag.pop_back();}}else{it.push_back(flag);}}vector<vector<int>> combine(int n, int k) {dfs(n, k, 1);return it;}
};