简介
回溯，搜索，递归，穷举，优化：剪枝。
树形结构 (N叉树）
- 宽度
-
深度
模板
选择，撤销在循环内。
def backtrack(status, params):
if (stopping conditions):
save result
return
for (choice in choices):
+choice
backtrack(status(choice), params)
-choice
- 组合
- 分割
- 子集
- 排列
- 棋盘
- 其它
回溯算法和 DFS 算法的细微差别是：回溯算法是在遍历「树枝」，DFS 算法是在遍历「节点」.
1、路径：也就是已经做出的选择。
2、选择列表：也就是你当前可以做的选择。
3、结束条件：也就是到达决策树底层，无法再做选择的条件。
for 选择 in 选择列表:
# 做选择
将该选择从选择列表移除
路径.add(选择)
backtrack(路径, 选择列表)
# 撤销选择
路径.remove(选择)
将该选择再加入选择列表
组合，子集，排列 (总共9个变种）
无重不可复选
有重不可复选
无重可复选
- 无重不可复选
组合，子集：用start index 控制选择列表. start: i+1 (不可复选）
排列：用used 数组避免选择同一位置数字 （不可复选）
# 组合，子集
def backtrack(nums: List[int], start: int):
# base case
# 回溯算法标准框架
for i in range(start, len(nums)):
# 做选择
track.append(nums[i])
# 注意参数
backtrack(nums, i + 1)
# 撤销选择
track.pop()
# 排列
def backtrack(nums: List[int]):
# base case
for i in range(len(nums)):
# 剪枝逻辑
if used[i]:
continue
# 做选择
used[i] = True
track.append(nums[i])
backtrack(nums)
# 撤销选择
track.pop()
used[i] = False
- 有重不可复选
需要去重：排序或者hash(如果不可以排序） （有重）
组合，子集：用start index 控制选择列表 + 同层去重 start: i+1 (不可复选）
排列: 用used数组标记避免重复选择 + 同层去重(细节）（不可复选）
nums.sort()
# 组合/子集问题回溯算法框架
def backtrack(nums: List[int], start: int):
# base case
# 回溯算法标准框架
for i in range(start, len(nums)):
# 剪枝逻辑，跳过值相同的相邻树枝
if i > start and nums[i] == nums[i - 1]:
continue
# 做选择
track.append(nums[i])
# 注意参数
backtrack(nums, i + 1)
# 撤销选择
track.pop()
nums.sort()
# 排列问题回溯算法框架
def backtrack(nums: List[int]):
# base case
for i in range(len(nums)):
# 剪枝逻辑
if used[i]:
continue
# 剪枝逻辑，固定相同的元素在排列中的相对位置
if i > 0 and nums[i] == nums[i - 1] and not used[i - 1]:
continue
# 做选择
used[i] = True
track.append(nums[i])
backtrack(nums)
# 撤销选择
track.pop()
used[i] = False
- 无重可复选
组合，子集：类似有重不可复选，但是递归调用初始Index是当前节点。start: i (可复选）
排列：不需要用used数组。（可复选）
# 组合/子集问题回溯算法框架
def backtrack(nums: List[int], start: int):
# base case
# 回溯算法标准框架
for i in range(start, len(nums)):
# 做选择
track.append(nums[i])
# 注意参数
backtrack(nums, i)
# 撤销选择
track.pop()
# 排列问题回溯算法框架
def backtrack(nums: List[int]):
# base case
for i in range(len(nums)):
# 做选择
track.append(nums[i])
backtrack(nums)
# 撤销选择
track.pop()
77. 组合
- 思路
- example
- 回溯，去重
- 宽度：n
-
深度：k
- 复杂度. 时间：, 空间:
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def backtrack(start):
if len(path) == k:
res.append(path[:])
return
for i in range(start+1, n+1):
path.append(i)
backtrack(i)
path.pop()
res = []
path = []
backtrack(0)
return res
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def traversal(start):
if len(path) == k:
res.append(path[:])
return
for i in range(start, n+1):
path.append(i)
traversal(i+1)
path.pop()
res = []
path = []
traversal(1)
return res
- 优化：剪枝
-
横向遍历的时候去掉不可能成功（个数不足）的情况。
-
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
def backtrack(start):
if len(path) == k:
res.append(path[:])
return
for i in range(start, n-(k-len(path))+2):
path.append(i)
backtrack(i+1)
path.pop()
res, path = [], []
backtrack(1)
return res
