全排列

46. 全排列 - 力扣（LeetCode）

问题简述

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

思路 1

• 递归+回溯模板：

• 把递归过程看作一棵树的生成过程，考虑两个关键问题：

  1. 每个节点需要产生哪些分支；

  2. 何时结束一条路径上的递归（递归基）；

• 本题中，

  • 对第一个问题：每个节点产生的分支由在这条路径上未使用过的数字决定；因此可以使用一个全局变量记录已经用过的数字，遍历时跳过这些数字即可；

    • 路径上的每个节点代表一次递归的深入，所以需要使用全局变量来记录（或者把变量作为参数传递到下一层），这个过程可以看作是一次纵向剪枝；

    • 如果是横向剪枝，则可以使用一个局部变量来记录（相关问题：全排列 II）；

  • 对第二个问题：使用一个变量记录当前的递归深度（最简单）；或者判断全局变量中每个数字都使用过；

Python

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:

        ret = []
        used = [0] * len(nums)  # 记录各位置的使用情况
        nums_len = len(nums)

        def dfs(deep, tmp):  # deep: 递归深度
            if deep == nums_len:  # len(tmp) == nums_len 也可以，省一个变量
                ret.append(tmp[:])
                return

            for i in range(nums_len):
                if used[i]: continue
                
                used[i] = 1
                tmp.append(nums[i])
                dfs(deep + 1, tmp)
                tmp.pop()
                used[i] = 0
            
        dfs(0, [])
        return ret

思路 2：下一个排列

• 先排序，然后判断是否存在下一个排列，进而得到全部排列；

• 代码略；

相关问题

• 47. 全排列 II - 力扣（LeetCode）

  存在重复数字