景真

外观

全排列

约 1237 字大约 4 分钟

回溯

2025-02-26

46. 全排列

给定一个不含重复数字的数组 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数组是每次递归时都初始化，所以它的作用域是本次递归，不会影响到下次递归，它是为了避免本次for循环选到重复的元素， 例如[4,6,7,7]，已经选了[4,6]，本次选了7，本轮中的for循环后面就选不到7了。本题中used数组的影响是横向的， 46.全排列中used数组的影响是纵向的，它是为了避免下次递归而不是本轮递归中的下次for循环选到重复元素，所以要跨递归，所以要是全局状态， 并作为方法参数进入每层递归。组合问题的状态空间是当前值及后面的值，排列问题的状态空间是除去重复值的所有值

回溯方法（如排列组合问题）不像岛屿那样需要从一个节点进入，它是从for循环时才开始选定节点，而岛屿问题（DFS）是先选定一个节点，再进行for循环。

组合/子集问题使用 start 变量保证元素 nums[start] 之后只会出现 nums[start+1..] 中的元素，通过固定元素的相对位置保证不出现重复的子集。

因为DFS是需要从一个节点进入，所以它的前序代码是在for循环外的。

class Solution {
    // 主函数，输入一组不重复的数字，返回它们的全排列
    public List<List<Integer>> permute(int[] nums) {
        // 准备回溯需要的工具：记录「路径」，即一个排列
        List<Integer> track = new LinkedList<>();
        // 准备回溯需要的工具：「路径」中的元素会被标记为 true，避免重复使用
        boolean[] used = new boolean[nums.length];
        // 定义结果链表，每个元素都是一条路径
        List<List<Integer>> res = new LinkedList<>();
        
        // 开始回溯，回溯中修改结果链表
        backtrack(nums, track, used, res);
        return res;
    }

    // 路径：记录在 track 中
    // 选择列表：nums 中不存在于 track 的那些元素（used[i] 为 false）
    // 结束条件：nums 中的元素全都在 track 中出现
    static void backtrack(int[] nums, LinkedList<Integer> track, boolean[] used, List<List<Integer>> res) {
        // 结束条件
        if (track.size() == nums.length) {
            // 把路径放到结果链表中去，注意要新建一个链表。
            res.add(new LinkedList(track));
            return;
        }

        // 遍历原数组，每次递归都从头开始遍历。
        for (int i = 0; i < nums.length; i++) {
            // 排除路径中已有的元素。题目说不含重复数字。
            if (used[i]) {
                // nums[i] 已经在 track 中，跳过
                continue;
            }
            
            // 做选择
            track.add(nums[i]);
            used[i] = true;
            // 进入下一层决策树
            backtrack(nums, track, used, res);
            // 取消选择
            track.removeLast();
            used[i] = false;
        }
    }
}
  • 时间复杂度： O(n×n!)O(n \times n!) ，其中 nn 为序列的长度。

在每次递归调用中，backtrack 函数会尝试将第 first 个位置的数与所有可能的数进行交换，从而生成所有排列。

  1. 初始调用：在初始调用时，first 为 0。我们会遍历 i 从 0 到 n-1，共 n 次调用。
  2. 第二次调用：在每个初始调用内部，first 递增为 1，我们会遍历 i 从 1 到 n-1，共 n-1 次调用。
  3. 第三次调用：依此类推，first 递增到 2 时，我们会遍历 i 从 2 到 n-1，共 n-2 次调用。

这样下去，总的递归调用次数就是排列的数量，即 n!。

对于每个排列，当所有元素都填满时（即 first == n），我们将当前的排列添加到结果列表中。这需要将一个长度为 n 的列表复制到结果列表中，时间复杂度为 O(n)。

回溯函数的总调用次数是 n!。在每次调用中，当到达叶结点时，我们需要 O(n) 的时间来复制当前的排列。因此，总的时间复杂度是O(n×n!)

  • 空间复杂度：O(n)O(n)，其中 nn 为序列的长度。除答案数组以外，递归函数在递归过程中需要为每一层递归函数分配栈空间， 所以这里需要额外的空间且该空间取决于递归的深度，这里可知递归调用深度为 O(n)O(n)。