78. 子集

class Solution:def subsets(self, nums: List[int]) -> List[List[int]]:ans = []cur = []def dfs(i):if i == len(nums):ans.append(cur.copy())return# 包括 nums[i]cur.append(nums[i])dfs(i+1)# 不包括 nums[i]cur.pop()dfs(i+1)dfs(0)return ans

要找出所有子集，對于數組里的每個元素，都只有選或不選兩種情況，所以從下標 i = 0 開始，包括或不包括 nums[i]，然后對下一個位置 i + 1 進行同樣操作。由于 cur 數組是會變的，所以要 copy 或者 cur[:]

77. 組合

class Solution:def combine(self, n: int, k: int) -> List[List[int]]:ans = []cur = []def dfs(start):if len(cur) == k:ans.append(cur.copy())returnif start > n:returnfor i in range(start, n + 1):cur.append(i)dfs(i + 1)cur.pop()dfs(1)return ans

對于組合，考慮了數字 i，后面添加的數要大于 i

39. 組合總和

class Solution:def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:ans = []cur = []def dfs(i, total):if total == target:ans.append(cur.copy())returnif i >= len(candidates) or total > target:returncur.append(candidates[i])dfs(i, total + candidates[i])cur.pop()dfs(i + 1, total)dfs(0, 0)return ans

46. 全排列

class Solution:def permute(self, nums: List[int]) -> List[List[int]]:ans = []cur = []counter = collections.Counter(nums)def dfs():if len(cur) == len(nums):ans.append(cur.copy())returnfor i in counter:if counter[i] > 0:cur.append(i)counter[i] -= 1dfs()cur.pop()counter[i] += 1dfs()return ans

排列從思路上是逐個添加，但是代碼實現上要用逐個排除的方法。

90. 子集 II

class Solution:def subsetsWithDup(self, nums: List[int]) -> List[List[int]]:ans = []cur = []nums.sort()def dfs(i):if i == len(nums):ans.append(cur.copy())returncur.append(nums[i])dfs(i+1)cur.pop()while i + 1 < len(nums) and nums[i] == nums[i + 1]:i += 1dfs(i+1)dfs(0)return ans

40. 組合總和 II

class Solution:def combinationSum2(self, candidates: List[int], target: int) -> List[List[int]]:candidates.sort()ans = []cur = []def dfs(pos, total):if total == target:ans.append(cur.copy())returnif pos >= len(candidates) or total > target:returnpre = -1for i in range(pos, len(candidates)):if candidates[i] == pre:continuecur.append(candidates[i])dfs(i + 1, total + candidates[i])cur.pop()pre = candidates[i]dfs(0, 0)return ans

47. 全排列 II

class Solution:def permuteUnique(self, nums: List[int]) -> List[List[int]]:ans = []cur = []counter = collections.Counter(nums)def dfs():if len(cur) == len(nums):ans.append(cur.copy())returnfor i in counter:if counter[i] > 0:cur.append(i)counter[i] -= 1dfs()cur.pop()counter[i] += 1dfs()return ans

總結

以上是生活随笔為你收集整理的回溯的问题合集（Leetcode题解-Python语言）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。