46. 全排列 Medium

给定一个不含重复数字的数组 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]]

解题思路

输入：一个没有重复数字的整数数组 nums。

输出：返回所有可能的排列结果。

这道题属于 排列型回溯 问题。

• 我们需要在每个位置上选择一个数字，保证每个数字只出现一次。
• 用一个 path 保存当前排列的结果。
• 用一个集合 s 记录还剩下哪些数字可以选。
• 当 path 的长度等于 nums 的长度时，说明当前路径是一个完整的排列，就把它保存到答案中。
• 每次选择完一个数字，就将它从可选集合 s 中删除，然后递归到下一层。
• 回溯时，要撤销选择，把数字从 path 中移除。

回溯三问

1. 当前操作？

   • 在当前位置 i（表示排列中已经选了多少个数字），从还没被选过的数字集合 s 中，依次尝试选择一个数字 x 放入当前排列 path 中。
   • 也就是把数字 x 放到 path 里，表示“我选择了这个数字”。

2. 子问题？

   • 选择了数字 x 之后，需要继续递归构造排列的剩余部分。
   • 也就是在集合 s - {x} 里继续选择下一个数字。

3. 下一个子问题？

   • 下一步递归就是调用 dfs(i + 1, s - {x})，表示继续在剩下的数字中选择，直到排列长度等于 n。

剪枝条件

• 只有当数字 x 还存在于集合 s 中时，才可以选择它。
• 当排列长度达到 n 时，就把当前排列加入答案。
• 由于题目保证数字没有重复，所以不需要对结果进行去重。

代码实现

python

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        ans = []      # 用来存放所有排列结果
        path = []     # 用来存放当前路径上的数字（当前排列）
        n = len(nums) # 数组长度

        def dfs(i, s):
            """
            i: 当前递归层数，表示排列中已经选了多少个数字
            s: 当前还剩下哪些数字可以选（集合）
            """
            if i == n:
                # 当排列长度达到数组长度时，说明当前路径是一个完整排列
                ans.append(path.copy())
                return

            for x in nums:
                # 只有当数字 x 还没被选过（存在于 s 中）时才选它
                if x in s:
                    path.append(x)          # 选择数字 x
                    dfs(i + 1, s - {x})    # 递归下一层，集合 s 减去已选数字 x
                    path.pop()             # 回溯，撤销选择，尝试别的数字

        dfs(0, set(nums))  # 从第0层开始，所有数字都可以选
        return ans

javascript

/**
 * @param {number[]} nums
 * @return {number[][]}
 */
var permute = function(nums) {
    const ans = [];          // 存放所有的排列结果
    const path = [];         // 当前排列的路径
    const unUsed = new Set(nums);  // 记录还没有被选择的数字（用 Set 保证查找快）

    /**
     * @param {number} i 当前递归的层数（表示当前排列中已经选择了多少个数字）
     * @param {Set} s   当前剩余的可选数字集合
     */
    function dfs(i, s) {
        // 如果已经选够了 nums.length 个数字，说明找到了一种排列
        if (i === nums.length) {
            ans.push([...path]);  // 把当前排列保存到结果数组中（深拷贝）
            return;
        }

        // 枚举所有剩余的数字
        for (let x of nums) {
            if (s.has(x)) {       // 只有没有被选过的数字才能选择
                path.push(x);     // 选择当前数字
                s.delete(x);      // 标记当前数字为“已使用”
                
                dfs(i + 1, s);    // 递归到下一层，继续选择数字

                // 回溯：撤销选择
                s.add(x);         // 恢复当前数字为“未使用”
                path.pop();       // 移除当前数字
            }
        }
    }

    dfs(0, unUsed);  // 从第0层开始，初始可选数字是所有的数字
    return ans;      // 返回所有的排列结果
};

复杂度分析

时间复杂度：O(n * n!)

空间复杂度：O(n * n!)

链接

46 国际版

46 中文版