您现在的位置是：亿华云 > 人工智能

我们一起学习排列问题！你会吗？

亿华云2025-10-03 07:03:44【人工智能】4人已围观

简介给定一个没有重复数字的序列，返回其所有可能的全排列。示例:输入: [1,2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2],

给定一个没有重复数字的学习序列，返回其所有可能的排列全排列。

示例:

输入: [1,问题2,3] 输出: [ [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1] ]

思路

此时我们已经学习了组合问题、分割回文串和子集问题，学习接下来看一看排列问题。排列

相信这个排列问题就算是问题让你用for循环暴力把结果搜索出来，这个暴力也不是学习很好写。

所以正如我们在关于回溯算法，排列你该了解这些!所讲的问题为什么回溯法是暴力搜索，效率这么低，学习还要用它?排列

因为一些问题能暴力搜出来就已经很不错了!

我以[1,2,3]为例，抽象成树形结构如下：

全排列

回溯三部曲

递归函数参数

首先排列是问题有序的，也就是学习说[1,2] 和[2,1] 是两个集合，这和之前分析的排列子集以及组合所不同的高防服务器地方。

可以看出元素1在[1,问题2]中已经使用过了，但是在[2,1]中还要在使用一次1，所以处理排列问题就不用使用startIndex了。

但排列问题需要一个used数组，标记已经选择的元素，如图橘黄色部分所示:

全排列

代码如下：

vector<vector<int>> result; vector<int> path; void backtracking (vector<int>& nums, vector<bool>& used) 递归终止条件

全排列

可以看出叶子节点，就是收割结果的地方。

那么什么时候，算是到达叶子节点呢?

当收集元素的数组path的大小达到和nums数组一样大的时候，说明找到了一个全排列，也表示到达了叶子节点。

代码如下：

// 此时说明找到了一组 if (path.size() == nums.size()) { result.push_back(path); return; } 单层搜索的逻辑

这里和组合问题、切割问题和子集问题最大的不同就是云服务器for循环里不用startIndex了。

因为排列问题，每次都要从头开始搜索，例如元素1在[1,2]中已经使用过了，但是在[2,1]中还要再使用一次1。

而used数组，其实就是记录此时path里都有哪些元素使用了，一个排列里一个元素只能使用一次。

代码如下：

for (int i = 0; i < nums.size(); i++) { if (used[i] == true) continue; // path里已经收录的元素，直接跳过 used[i] = true; path.push_back(nums[i]); backtracking(nums, used); path.pop_back(); used[i] = false; }

整体C++代码如下：

class Solution { public: vector<vector<int>> result; vector<int> path; void backtracking (vector<int>& nums, vector<bool>& used) { // 此时说明找到了一组 if (path.size() == nums.size()) { result.push_back(path); return; } for (int i = 0; i < nums.size(); i++) { if (used[i] == true) continue; // path里已经收录的元素，直接跳过 used[i] = true; path.push_back(nums[i]); backtracking(nums, used); path.pop_back(); used[i] = false; } } vector<vector<int>> permute(vector<int>& nums) { result.clear(); path.clear(); vector<bool> used(nums.size(), false); backtracking(nums, used); return result; } };