此博客为《代码随想录》二叉树章节的学习笔记，主要内容为回溯算法排列问题相关的题目解析。

文章目录

• 46.全排列
• 47.全排列 II

46.全排列

题目链接

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        res, path = [], []
        used = [0] * len(nums)
        
        def dfs() -> None:
            if len(path) == len(nums):
                res.append(path.copy())
                return
            nonlocal used
            for i in range(len(nums)):
                if used[i] == 0:
                    used[i] = 1
                    path.append(nums[i])
                    dfs()
                    path.pop()
                    used[i] = 0
        
        dfs()
        return res

• 排列问题由于需要考虑元素不同的顺序，因此从 start 升级为 used 数组，标识元素是否被使用过

47.全排列 II

题目链接

class Solution:
    def permuteUnique(self, nums: List[int]) -> List[List[int]]:
        res, path = [], []
        used = [0] * len(nums)
        nums.sort()
        
        def dfs() -> None:
            if len(path) == len(nums):
                res.append(path.copy())
                return
            nonlocal used
            for i in range(len(nums)):
                if i > 0 and nums[i] == nums[i-1] and used[i-1] == 0:
                    continue
                if used[i] == 0:
                    used[i] = 1
                    path.append(nums[i])
                    dfs()
                    path.pop()
                    used[i] = 0
        
        dfs()
        return res

• 添加排序和树层去重
• 排列问题中的树层去重需要添加条件 used[i-1] == 0
  • used[i-1] == 0 说明同一树层 nums[i-1] 使用过，之后在回溯的过程中又设置为 0
  • used[i-1] == 1 说明同一树枝 nums[i-1] 使用过，已经是之前步骤的选择，对现在的选择没有影响