全排列 | 秋招知识库

视频讲解

Python 解法1C++ 解法1

python

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        path = [0] * n  # 所有排列的长度都是一样的 n
        on_path = [False] * n
        ans = []

        # 枚举 path[i] 填 nums 的哪个数
        def dfs(i: int) -> None:
            if i == n:
                ans.append(path.copy())  # 也可以写 path[:]
                return
            for j, on in enumerate(on_path):
                if not on:
                    path[i] = nums[j]  # 从没有选的数字中选一个
                    on_path[j] = True  # 已选上
                    dfs(i + 1)
                    on_path[j] = False  # 恢复现场
                    # 注意 path 无需恢复现场，因为排列长度固定，直接覆盖就行

        dfs(0)
        return ans

cpp

// C++ 版待补充

Python 解法2C++ 解法2

python

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        path = [0] * n
        ans = []

        # 枚举 path[i] 填 remain（剩余数字）中的哪个数
        def dfs(i: int, remain: Set[int]) -> None:
            if i == n:
                ans.append(path.copy())
                return

            for x in remain:
                path[i] = x
                dfs(i + 1, remain - {x})

        dfs(0, set(nums))
        return ans

cpp

// C++ 版待补充

C++ 解法3

cpp

class Solution {
public:
    vector<vector<int>> permute(vector<int> &nums) {
        int n = nums.size();
        vector<int> path(n); // 所有排列的长度都是一样的 n
        vector<int8_t> on_path(n);
        vector<vector<int>> ans;

        // 枚举 path[i] 填 nums 的哪个数
        auto dfs = [&](this auto&& dfs, int i) -> void {
            if (i == n) {
                ans.emplace_back(path);
                return;
            }

            for (int j = 0; j < n; j++) {
                if (!on_path[j]) {
                    path[i] = nums[j]; // 从没有选的数字中选一个
                    on_path[j] = true; // 已选上
                    dfs(i + 1);
                    on_path[j] = false; // 恢复现场
                    // 注意 path 无需恢复现场，因为排列长度固定，直接覆盖就行
                }
            }
        };

        dfs(0);
        return ans;
    }
};

复杂度分析

时间复杂度： $O (n \cdot n!)$ ，其中 $n$ 为 $nums$ 的长度。视频中提到，搜索树中的节点个数低于 $3 \cdot n!$ 。实际上，精确值为 $⌊ e \cdot n! ⌋$ ，其中 $e = 2.718 \dots$ 为自然常数。有 $O (n!)$ 个叶节点，每个叶节点花费 $O (n)$ 的时间复制 $path$ 数组，因此时间复杂度为 $O (n \cdot n!)$ 。
空间复杂度： $O (n)$ 。返回值的空间不计入。

专题训练

见下面回溯题单的「§4.5 排列型回溯」。

分类题单

如何科学刷题？

我的题解精选（已分类）

欢迎关注 B站@灵茶山艾府

视频讲解 ​

复杂度分析 ​

专题训练 ​

分类题单 ​

视频讲解

复杂度分析

专题训练

分类题单