《代码随想录》回溯问题学习总结

How to work out the problem of backtracing?

1. 组合问题

回溯的本质仍然是递归
考虑递归三部曲:

• 递归传递参数和返回值 backtracing() -> None:
  
• 递归的结束条件
  
• 在每次递归中需要执行的逻辑
  

1.1 分析回溯问题

以最简单的组合问题为例，在抽象树的每一层中是遍历每种可能取值，而在树枝（深度）中遍历则是寻找每种组合的子组合
1.2 回溯问题的模版代码

仍然组合问题为例

1. # 组合问题
2. def combine(self, n: int, k: int) -> list[list[int]]:
3.     result = []
4.     self.backtracing(n, k, 1, [], result)
5.     return result
7. # paragram
8. def backtracing(self, n, k, startindex, path: list, result: list):
9.     # stop condition
10.     if len(path) == k:
11.         result.append(path[:])
12.         return
13.    
14.     for i in range(startindex, n - (k - len(path)) + 2): # 剪枝
15.         path.append(i)
16.         self.backtracing(n, k, i+1, path, result)
17.         path.pop()

复制代码

1.3 什么时候需要startindex

每次在集合中选取元素，可选择的范围随着选取的进行而收缩（可选取元素减少），调整可选取的范围，就是要靠startindex
1.4 在for - 层遍历过程中添加额外判断逻辑

以Leetcode第40题组合总和为例，需要对元素进行去重

1.     # LC.40.组合总和2
2. def combinationSum2(self, candidates: list[int], target: int) -> list[list[int]]:
3.     candidates = sorted(candidates)
4.     temp, res = [], []
6.     def backtracing(startindex: int, used: list) -> None:
7.         
8.         if target == sum(temp):
9.             res.append(temp.copy())
10.             return
11.         
12.         elif target < sum(temp):
13.             return
14.             
16.         for i in range(startindex, len(candidates)):
17.             if i > 0 and candidates[i-1] == candidates[i] and used[i-1] == False:
18.                 continue
20.             temp.append(candidates[i])
21.             used[i] = True
22.             backtracing(i+1, used)
23.             used[i] = False
24.             temp.pop()
25.    
26.     backtracing(0, [False for i in range(len(candidates))])

复制代码

在本题中，同一个解可以出现同一元素（按树枝搜索），但在解集合中不能出现相同元素，如[[1,1,2],[1,2,1]]是不合法的，使用candidates[]与used[]数组来控制按层搜索和按树枝搜索时出现重复元素是否可以被添加到解集合中，体现在代码中：

1. for i in range(startindex, len(candidates)):
2.         if i > 0 and candidates[i-1] == candidates[i] and used[i-1] == False:
3.             continue

复制代码

2. 子集问题

2.1 子集问题概述

子集问题和排列问题的不同之处是需要收集抽象树上的每一个节点，而非叶子节点。即每次回溯都需要判断当前节点是否是解，而非在每次回溯判断是否到达叶子节点。
2.2 子集问题模版

以力扣第70题为例，在每次调用backtracing()函数后都需要收集当前节点

1. def subsets(self, nums: list[int]) -> list[list[int]]:
2.     res, path = [], []
4.     # 回溯
5.     def backtracing(startindex: int) -> None:
6.         # 每次调用backtracing都是在遍历该树的一个节点
7.         res.append(path.copy())
9.         if startindex == len(nums):
10.             return
11.         
12.         for i in range(startindex, len(nums)):
13.             path.append(nums[i])
14.             backtracing(i+1)
15.             path.pop()
16.    
17.     backtracing(0)
18.     return res

复制代码

2.3 子集问题去重

子集问题的去重同组合问题相同，但需要对集合进行排序，考虑在抽象树的每一数层上不可以使用相同元素，以力扣第90题为例，分别使用used标志数组和set()集合去重
2.3.1 used标志数组去重

1. # 去重问题，同一树层不能重复（不同的解集合），但在同一树枝可以重复（寻找唯一子集的过程，树的遍历深度加深）
2. def subsetsWithDup(self, nums: list[int]) -> list[list[int]]:
3.     nums.sort()
4.     res, path = [], []
7.     # 回溯
8.     def backtracing(startindex: int, used: list[bool]) -> None:
9.         # 每次调用backtracing都是在遍历该树的一个节点
10.         res.append(path.copy())
12.         if startindex == len(nums):
13.             return
14.         
15.         for i in range(startindex, len(nums)):
16.             # 去重
17.             if i > 0 and nums[i-1] == nums[i] and used[i-1] is False:
18.                 continue
20.             path.append(nums[i])
21.             used[i] = True
22.             backtracing(i+1, used)
23.             # 回溯
24.             used[i] = False
25.             path.pop()
26.    
27.     backtracing(0, [False for i in range(len(nums))])
28.     return res

复制代码

2.3.2 set()集合去重

1. def subsetsWithDup(self, nums):
2.     nums.sort()  # 去重需要排序
3.     result = []
4.     self.backtracking(nums, 0, [], result)
5.     return result
7. def backtracking(self, nums, startIndex, path, result):
8.     result.append(path[:])
9.     used = set()
10.     for i in range(startIndex, len(nums)):
11.         if nums[i] in used:
12.             continue
13.         used.add(nums[i])
14.         path.append(nums[i])
15.         self.backtracking(nums, i + 1, path, result)
16.         path.pop()

复制代码

3. 排列问题

3.1 概述

排列问题与组合问题的区别在于每次for循环遍历时不使用startindex来寻找下一个遍历起始位置，而是从0开始
3.2 模版

1. def permute(self, nums: list[int]) -> list[list[int]]:
2.     res, path = [], []
4.     def backtracing() -> None:
5.         if len(path) is len(nums):
6.             res.append(path.copy())
7.             return
8.         
9.         for i in range(len(nums)):
10.             # 数字不重复
11.             if nums[i] in path:
12.                 continue
14.             path.append(nums[i])
15.             backtracing()
16.             path.pop()
18.     backtracing()
19.     return res

复制代码

3.3 去重

去重逻辑和之前相同，但需要注意的是，在同一树枝上进行遍历时也需要去重，即使用if used == Fasle来避免在同一树枝进行遍历时使用到相同元素如nums=[1,1,2]中，选取顺序：nums[0], nums[1], nums[2]与nums[1], nums[0], nums[2]会导致排列集重复

1. def permuteUnique(self, nums: list[int]) -> list[list[int]]:
2.     nums.sort()
3.     res, path = [], []
5.     def backtracing(used: list) -> None:
6.         if len(path) is len(nums):
7.             res.append(path.copy())
8.             return
9.         for i in range(len(nums)):
10.             if (i > 0 and nums[i-1] == nums[i] and not used[i-1]):
11.                 continue
13.             if used[i] == False: # 同一树枝i没使用过
14.                 used[i] = True
15.                 path.append(nums[i])
16.                 backtracing(used)
17.                 path.pop()
18.                 used[i] = False
20.     backtracing([False for i in range(len(nums))])
21.     return res

复制代码

来源：程序园用户自行投稿发布，如果侵权，请联系站长删除
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！