回溯算法

模板

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# nums 选项
def dining(nums):
desk = []
# dish: 打菜盘,menus: 菜单
def backtrack(dish, menus):
if (满足结束条件):
desk.append(dish)
for val in menus:
# 做选择
dish.append(val)
backtrack(dish, 新菜单)
# 撤销选择
dish.pop()
backtrack([], nums)
return desk

为了便于理解上述回溯算法的模板,假设我们去食堂的打菜,在满足指定条件的情况下(视题目而定),把菜放到桌子上。

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

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

应用

子集

LeetCode 地址

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, menus):
if (dish not in desk):
desk.append(dish[:])

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

trackBack([], nums)
return desk

全排列

LeetCode 地址

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

组合

LeetCode 地址

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

for val in menus:
dish.append(val)
backtrack(dish, range(val + 1, n + 1))
dish.pop()
backtrack([], range(1, n + 1))
return desk

变形

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

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

不包含重复元素的情况

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

1
newMenus = menus[(idx+1):]

如果解集不忽略子项的排序差异(例如求全排列) ,新菜单为:

1
2
newMenus = menus[:]
newMenus.remove(val)

包含重复元素的情况

例子:零钱兑换 II

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
def change(amount, coins):
desk = []
coins.sort()
def backtrack(dish, menus):
if sum(dish) > amount:
return
elif sum(dish) == amount:
dish.sort() # 忽略子项的排序差异时,先排序在判断是否在结果中
if dish not in desk:
desk.append(dish[:])
return
for idx, val in enumerate(menus):
dish.append(val)
# 新菜单:小于剩余值面额的零钱
residue = amount - sum(dish)
backtrack(dish, [i for i in menus if i <= residue])
dish.pop()
backtrack([], coins)
print(desk) # 打印所有符合的组合
return len(desk)

print(change(5, [1,2,5]))