回溯算法

Posted on Edited on

模板

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

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:]

优化

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

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

练习题

编号为 Leecode 题号

  1. 全排列（中等）
  2. 全排列 II（中等
  3. 组合总和（中等）
  4. 组合总和 II（中等）
  5. 组合（中等）
  6. 子集（中等）
  7. 子集 II（中等）：剪枝技巧同 47 题、39 题、40 题；
  8. 第 k 个排列（中等）
  9. 复原 IP 地址（中等）