全排列

🟡 中等

题目描述

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

解法

参考答案 (2 个标签)

回溯 O(n×n!)

思路

使用回溯算法，每次选择一个未使用过的数字加入路径，直到路径长度等于数组长度。

代码实现

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
function permute(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;
}

复杂度分析

时间复杂度：O(n × n!)，共有 n! 个排列，每个排列需要 O(n) 复制
空间复杂度：O(n)，递归深度和 used 数组

图解

nums = [1, 2, 3]

决策树：
              []
         /    |    \
       [1]   [2]   [3]
      /  \   /  \   /  \
   [1,2][1,3][2,1][2,3][3,1][3,2]
    |    |    |    |    |    |
 [1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]

下一章节子集