46.全排列

发表于 分类于 阅读次数：

给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

1
2
输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

示例 2：

1
2
输入：nums = [0,1]
输出：[[0,1],[1,0]]

示例 3：

1
2
输入：nums = [1]
输出：[[1]]

解题思路

这是一道经典的回溯题目，考察对全排列的理解和实现。

核心思想

  • 使用回溯算法生成所有可能的排列
  • 通过交换元素或使用visited数组来避免重复
  • 当路径长度等于数组长度时，添加到结果中

方法一：回溯法（推荐）

时间复杂度 O(n!)、空间复杂度 O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    const result = [];
    const used = new Array(nums.length).fill(false);
    
    function backtrack(path) {
        // 如果路径长度等于数组长度，添加到结果中
        if (path.length === nums.length) {
            result.push([...path]);
            return;
        }
        
        // 遍历所有可能的数字
        for (let i = 0; i < nums.length; i++) {
            // 如果数字已经被使用，跳过
            if (used[i]) continue;
            
            // 选择当前数字
            used[i] = true;
            path.push(nums[i]);
            
            // 递归
            backtrack(path);
            
            // 撤销选择
            path.pop();
            used[i] = false;
        }
    }
    
    backtrack([]);
    return result;
};

方法二：交换法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
var permute = function(nums) {
    const result = [];
    
    function backtrack(start) {
        // 如果start等于数组长度，添加到结果中
        if (start === nums.length) {
            result.push([...nums]);
            return;
        }
        
        // 从start开始，与后面的每个位置交换
        for (let i = start; i < nums.length; i++) {
            // 交换元素
            [nums[start], nums[i]] = [nums[i], nums[start]];
            
            // 递归
            backtrack(start + 1);
            
            // 撤销交换
            [nums[start], nums[i]] = [nums[i], nums[start]];
        }
    }
    
    backtrack(0);
    return result;
};

方法三：使用Set

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
var permute = function(nums) {
    const result = [];
    
    function backtrack(path, remaining) {
        if (remaining.size === 0) {
            result.push([...path]);
            return;
        }
        
        for (const num of remaining) {
            path.push(num);
            remaining.delete(num);
            
            backtrack(path, remaining);
            
            path.pop();
            remaining.add(num);
        }
    }
    
    backtrack([], new Set(nums));
    return result;
};

方法四：递归法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
var permute = function(nums) {
    if (nums.length === 1) {
        return [nums];
    }
    
    const result = [];
    
    for (let i = 0; i < nums.length; i++) {
        const current = nums[i];
        const remaining = nums.slice(0, i).concat(nums.slice(i + 1));
        
        const perms = permute(remaining);
        
        for (const perm of perms) {
            result.push([current, ...perm]);
        }
    }
    
    return result;
};

解题要点

  1. 回溯法：

    • 使用递归生成所有可能的排列
    • 通过visited数组或交换来避免重复
    • 当路径长度等于数组长度时，添加到结果中

  2. 避免重复：

    • 使用visited数组标记已使用的数字
    • 或者使用交换法，每次固定一个位置

  3. 时间复杂度：

    • 全排列数量：n!
    • 时间复杂度：O(n!)
    • 空间复杂度：O(n)

面试要点

  • 高频考点：这道题是面试中的高频回溯题
  • 回溯算法：考察对递归和回溯的理解
  • 排列组合：考察对全排列的理解
  • 时间复杂度：了解阶乘的复杂度

相关题目

扩展思考

  1. 为什么使用回溯法？

    • 需要生成所有可能的排列
    • 通过visited数组避免重复选择
    • 递归结构清晰，易于理解

  2. 时间复杂度分析

    • 全排列数量：n!
    • 时间复杂度：O(n!)
    • 空间复杂度：O(n)

  3. 不同方法的比较

    • visited数组法：直观，易于理解
    • 交换法：空间复杂度更低
    • Set法：代码简洁
    • 递归法：逻辑清晰

  4. 边界情况

    • 空数组：返回[[]]
    • 单个元素：返回[[element]]
    • 两个元素：返回[[a,b], [b,a]]

  5. 实际应用

    • 密码生成
    • 游戏排列
    • 数据加密

  6. 变种问题

    • 包含重复数字的全排列
    • 部分排列
    • 带限制条件的排列

最后更新: 2021-09-30