回溯算法

模板

回溯算法可以用来解决子集、排列、组合问题,主要形式是从一堆选项中挑选出符合要求的组合,基础模板如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 假设这样一个场景:去食堂的打菜,需要把满足条件的菜的组合放到桌子上
def dining(nums):
desk = []
# dish: 餐盘,menu: 菜单
def backtrack(dish, menu):
if (满足结束条件):
# 把菜的组合放到桌子上, dish 需要拷贝
desk.append(dish[:])
for val in menu:
# 做选择(把一个菜放入餐盘)
dish.append(val)
# 根据题目,调整新菜单的值
backtrack(dish, 新菜单)
# 撤销选择(把一个菜取出餐盘)
dish.pop()
backtrack([], nums)
return desk

解空间结构:常用的有两种,子集树(零一背包问题)和排列树(货郎问题)

  • 子集树:从n个元素的集合S中找出满足某种性质的子集时,复杂度 O(2^n)
  • 排列树:从n个元素的集合S中找出满足某种性质的排列时,复杂度 O(n!)

应用

子集

LeetCode 78 题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution:
def subsets(self, nums: List[int]) -> List[List[int]]:
desk = []
def trackBack(dish, menu):
if (dish not in desk):
desk.append(dish[:])

for idx, val in enumerate(menu):
dish.append(val)
trackBack(dish, menu[(idx+1):])
dish.pop()

trackBack([], nums)
return desk

组合

LeetCode 77 题

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
def combine(self, n: int, k: int) -> List[List[int]]:
desk = []
def backtrack(dish, menu):
if (len(dish) == k):
desk.append(dish[:])
return

for val in menu:
dish.append(val)
trackBack(dish, menu[(idx+1):])
dish.pop()

backtrack([], range(1, n + 1))
return desk

全排列

LeetCode 46 题

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
def permute(self, nums: List[int]) -> List[List[int]]:
desk = []
long = len(nums)
def backtrack(dish, menu):
if dish not in desk and len(dish) == long:
desk.append(dish[:])
for idx, val in enumerate(menu):
dish.append(val)
backtrack(dish, menu[:idx] + menu[idx + 1:])
dish.pop()
backtrack([], nums)
return desk

变形

根据不同的题型,回溯算法中变化的部分是结束条件新菜单

新菜单指的是,每次可选项的集合,根据不同的题目,新菜单是不一样的。

不包含重复元素的情况

如果解集忽略子项的排序差异,则新菜单为:

1
newmenu = menu[(idx+1):]

如果解集不忽略子项的排序差异 ,则新菜单为:

1
menu[:idx] + menu[idx + 1:]

练习题

编号为 Leecode 题号

  1. 全排列(中等)
  2. 全排列 II(中等):思考为什么造成了重复,如何在搜索之前就判断这一支会产生重复;
  3. 组合总和(中等)
  4. 组合总和 II(中等)
  5. 组合(中等)
  6. 子集(中等)
  7. 子集 II(中等):剪枝技巧同 47 题、39 题、40 题;
  8. 第 k 个排列(中等):利用了剪枝的思想,减去了大量枝叶,直接来到需要的叶子结点;
  9. 复原 IP 地址(中等)

优化

回溯算法是一种穷举的算法,会遍历所有的情况,我们可以通过剪枝来跳过一些不合符要求的遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def dining(nums):
desk = []
def backtrack(dish, menu):
if (满足结束条件):
desk.append(dish[:])
for val in menu:
# 在此进行剪枝,跳过不符合要求的情况
if (满足剪枝条件):
continue
dish.append(val)
backtrack(dish, 新菜单)
dish.pop()
backtrack([], nums)
return desk