全排列

last modify

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:下一个排列

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

  • 代码略;

相关问题

Last updated