跳到主要内容

LeetCode 46. 全排列

本节目标

用 used 标记当前路径已经选择的下标，枚举所有顺序不同的排列。

这道题是回溯决策树的起点：每一层从尚未使用的数字中选一个，直到路径长度等于输入长度。

查看 LeetCode 原题

题意与约束​

给定互不相同的整数数组，返回它的全部排列。排列中元素相同而顺序不同也算不同结果，因此不能只用一个向后移动的起点限制候选范围。

朴素思路与瓶颈​

可以先枚举所有长度为 n 的数字序列，再检查序列是否重复使用元素，但大量无效序列会在最后才被丢弃。更直接的做法是在每一层选择时就排除已经进入当前路径的下标。

当前路径与 used​

path 是已经排好的前缀，used[index] 只描述当前这条递归路径，不是全局永久状态。选择 nums[index] 前标记它，递归返回后删除路径末尾并取消标记。这样同一元素不能在一条排列中出现两次，却能在另一条兄弟分支中出现在不同位置。

当 path 长度达到 nums.size()，它已经是一条完整排列，复制后加入答案。复制不可省略，因为返回上一层时 path 会继续被修改。

代码实现​

C++17
#include <vector>

using namespace std;

class Solution {
private:
    vector<vector<int>> answer;
    vector<int> path;
    vector<bool> used;

    void backtrack(vector<int>& nums) {
        if (path.size() == nums.size()) {
            answer.push_back(path);
            return;
        }

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

public:
    vector<vector<int>> permute(vector<int>& nums) {
        answer.clear();
        path.clear();
        used.assign(nums.size(), false);
        backtrack(nums);
        return answer;
    }
};

复杂度分析​

设输入长度为 n。一共有 n! 个排列，每个排列复制长度为 n 的路径，时间复杂度为 O(n · n!)。递归栈、路径和 used 额外使用 O(n) 空间；保存全部答案需要 O(n · n!) 空间。

易错点​

  • 忘记在回溯后恢复 used[index]，使其他分支错误地跳过该元素。
  • 把 used 改为 start，只会得到升序选择的一条路径，而不是所有顺序。
  • 叶子处直接保存可变 path 的引用，导致答案在回溯后被清空或改写。

模式迁移​

当元素允许重复时，需要先排序并在同一层跳过等值分支；当只需第 k 个排列时，可用阶乘分块直接确定每一位。无论变体如何变化，路径内的占用状态仍要与撤销动作严格配对。