此博客為《代碼隨想錄》二叉樹章節的學習筆記，主要內容為回溯算法排列問題相關的題目解析。

文章目錄

• 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())returnnonlocal usedfor i in range(len(nums)):if used[i] == 0:used[i] = 1path.append(nums[i])dfs()path.pop()used[i] = 0dfs()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())returnnonlocal usedfor i in range(len(nums)):if i > 0 and nums[i] == nums[i-1] and used[i-1] == 0:continueif used[i] == 0:used[i] = 1path.append(nums[i])dfs()path.pop()used[i] = 0dfs()return res

• 添加排序和樹層去重
• 排列問題中的樹層去重需要添加條件 used[i-1] == 0
  • used[i-1] == 0 說明同一樹層 nums[i-1] 使用過，之后在回溯的過程中又設置為 0
  • used[i-1] == 1 說明同一樹枝 nums[i-1] 使用過，已經是之前步驟的選擇，對現在的選擇沒有影響