leetcode 46 全排列 | 回溯

class Solution:
    def permute(self, nums: List[int]) -> List[List[int]]:
        def backtrace(nums,track,used):
            # 触发结束的条件
            if len(track) == len(nums):
                res.append(track.copy()) # 
                return
            for i in range(len(nums)):
                if used[i] :
                    continue
                # 做选择
                track.append(nums[i])
                used[i] = True
                # 进入下一层
                backtrace(nums,track,used)
                # 取消选择
                track.pop()
                used[i] = False
        res = []
        used = [False] * len(nums)
        track = []
        backtrace(nums,track,used)
        return res

解释

permute 是主方法，用于初始化回溯过程并返回结果。

• 初始化 res 为空列表，用于存储所有排列。
• 初始化 used 为布尔值列表，表示每个元素是否被使用。
• 初始化 track 为空列表，用于存储当前路径。
• 调用 backtrace 开始回溯过程。
• 返回结果列表 res。

backtrace 函数

backtrace 是一个递归函数，用于生成所有排列。

• 结束条件：

  • 当 track 的长度等于 nums 的长度时，说明已经生成了一个完整的排列，将其添加到结果列表 res 中。

• 回溯过程：

  • 遍历 nums 中的每个元素。
  • 如果当前元素已经被使用（used[i] 为 True），则跳过。
  • 将当前元素添加到 track 中，并标记为已使用（used[i] = True）。
  • 递归调用 backtrace。
  • 回溯：移除 track 中的最后一个元素，并将当前元素标记为未使用（used[i] = False）。

track.copy() 的重要性：

• 在将 track 添加到结果列表 res 时，需要使用 track.copy()，否则 res 中存储的将是同一个 track 的引用。在后续的回溯过程中，track 会被修改，导致 res 中的内容也发生变化。