Sign in Subscribe
算法

全排列

loser

• 7 min read
Share

给定一个不含重复数字的数组 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 中的所有整数互不相同

解法一（回溯 + used 标记）：

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        vector<int> path;
        vector<bool> used(nums.size(), false);
        backtrack(nums, used, path, ans);
        return ans;
    }

private:
    void backtrack(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& ans) {
        if (path.size() == nums.size())
        {
            ans.push_back(path);
            return;
        }

        for (int i = 0; i < nums.size(); ++i)
        {
            if (used[i])
            {
                continue;
            }
            used[i] = true;
            path.push_back(nums[i]);
            backtrack(nums, used, path, ans);
            path.pop_back();
            used[i] = false;
        }
    }
};

解法二（原地交换）：

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        backtrack(nums, 0, ans);
        return ans;
    }

private:
    void backtrack(vector<int>& nums, int start, vector<vector<int>>& ans) {
        if (start == nums.size())
        {
            ans.push_back(nums);
            return;
        }

        for (int i = start; i < nums.size(); ++i)
        {
            swap(nums[start], nums[i]);
            backtrack(nums, start + 1, ans);
            swap(nums[start], nums[i]);
        }
    }
};

核心思想

全排列问题用回溯（深度优先搜索）来解决。

它本质上是在遍历一棵「决策树」：

一共有 n 个位置需要填，每一步从未使用过的数字里选一个，填到当前位置，然后递归处理下一个位置。

当 n 个位置都填满时，就得到一个完整排列，把它加入答案。

回溯的关键在于「选择 - 递归 - 撤销」三步：

  1. 做选择：把某个数字放到当前位置
  2. 递归：处理下一个位置
  3. 撤销选择：把刚放进去的数字拿出来，以便尝试下一个数字

这样就能保证枚举到所有 n! 种排列，并且不重不漏。

回溯框架

两种解法都遵循同一个回溯模板：

backtrack(当前状态):
    if 已经得到一个完整解:
        记录答案
        return
    for 每个候选选择:
        做选择
        backtrack(更新后的状态)
        撤销选择

区别只在于「如何标记哪些数字已经用过」：

  • 解法一用一个 used 数组显式标记每个数字是否被选过
  • 解法二通过交换，把「已选的数字」固定在数组前面一段，不额外开数组

解法一：回溯 + used 标记

用 used[i] 表示下标 i 的数字是否已经在当前排列里。

递归终止条件

if (path.size() == nums.size())
{
    ans.push_back(path);
    return;
}

当 path 的长度等于 nums 的长度时，说明已经填满了所有位置，把当前排列加入答案。

枚举候选

for (int i = 0; i < nums.size(); ++i)
{
    if (used[i])
    {
        continue;
    }
    ...
}

每次从头遍历所有数字，跳过已经用过的数字，剩下的就是候选。

做选择、递归、撤销

used[i] = true;
path.push_back(nums[i]);
backtrack(nums, used, path, ans);
path.pop_back();
used[i] = false;

先标记该数字已使用并加入 path，递归处理下一层，回来后再撤销，恢复现场。

解法二：原地交换

原地交换法不额外使用 used 数组，而是把数组分成两部分：

  • [0, start) 这一段是已经确定好的前缀
  • [start, n) 这一段是还未安排的剩余数字

递归终止条件

if (start == nums.size())
{
    ans.push_back(nums);
    return;
}

当 start 走到数组末尾时，整个数组已经是一个完整排列，直接把它加入答案。

枚举候选并交换

for (int i = start; i < nums.size(); ++i)
{
    swap(nums[start], nums[i]);
    backtrack(nums, start + 1, ans);
    swap(nums[start], nums[i]);
}

思路是：位置 start 可以放剩余段 [start, n) 中的任意一个数字。

于是依次把 nums[i] 换到位置 start，递归处理后面的位置，回来后再换回来恢复现场。

边界情况

如果 nums 只有一个元素，例如 [1]：

  • 解法一中，只有 1 这一个候选，填满后得到 [[1]]
  • 解法二中，start 直接走到末尾，得到 [[1]]

如果 nums 有两个元素，例如 [0,1]：

  • 得到 [[0,1],[1,0]] 两种排列

题目保证 nums 中的数字互不相同，所以不需要额外处理重复数字的去重问题。

如果数组中存在重复数字，则需要额外的去重逻辑，但本题不涉及。

正确性证明

我们证明：算法枚举出且仅枚举出 nums 的所有全排列。

结论 1：每个答案都是一个合法的全排列

解法一中，path 的每个位置都填入了互不相同的数字（由 used 数组保证），且长度最终等于 n，因此是一个合法排列。

解法二中，每次交换后 [0, start) 都是互不相同的数字，递归到底后整个数组是一个合法排列。

结论 2：不会漏掉任何排列

解法一中，在每一层递归，for 循环遍历了所有尚未使用的数字，即当前层的每一种可能选择都被尝试。

解法二中，在每一层递归，for 循环遍历了 [start, n) 的所有数字，即当前位置的每一种填充方式都被尝试。

因此任意一个合法排列都能在决策树的某个叶节点处被构造出来，不会漏掉。

结论 3：不会产生重复的排列

解法一中，由于每一层选择的是不同下标，同一个数字不会在同一层被选两次，所以每个排列只会被构造一次。

解法二中，递归时 start 单调递增，每个排列通过确定的交换序列构造出来，且回溯时完整恢复现场，不会重复。

因此枚举结果不重不漏。

得出结论

由结论 1、2、3 可知，算法返回的结果恰好是 nums 的所有全排列。

因此两个解法都正确。

举例理解

以：

nums = [1,2,3]

为例，看解法一的决策树。

第一层，位置 0 可以填 1、2、3：

  • 填 1 后，剩下 [2,3]
  • 填 2 后，剩下 [1,3]
  • 填 3 后，剩下 [1,2]

以「第一层填 1」这条分支继续：

[1] -> 填 2 -> [1,2] -> 填 3 -> [1,2,3]  记录
     -> 填 3 -> [1,3] -> 填 2 -> [1,3,2]  记录

同样，「第一层填 2」得到：

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

「第一层填 3」得到：

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

最终一共得到 3! = 6 个排列：

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

和示例输出一致。

复杂度分析

解法一

全排列一共有 n! 个，每个排列需要 O(n) 时间复制到答案中。

  • 时间复杂度：O(n * n!)
  • 空间复杂度：O(n)，递归栈深度为 n，path 和 used 各占 O(n)，不计输出数组

解法二

同样有 n! 个排列，每个排列需要 O(n) 时间复制。

  • 时间复杂度：O(n * n!)
  • 空间复杂度：O(n)，递归栈深度为 n，没有额外的 used 数组，不计输出数组

其中 n = nums.length。

解法二不额外使用标记数组，空间略优；解法一更直观、更通用，是推荐写法。