动态规划是能够通过子问题的求解推出总问题的答案。而回溯算法的解题思路比较简单，就是不断地做选择，当走不通的时候，就回溯到上一个节点，走别的路。解决一个回溯问题，实际上就是一个多叉树的遍历问题。

基本概念

1.路径：也就是已经做出的选择（已经走过的节点）。
2.选择列表：也就是你当前可以做的选择（当前节点面临的多个分支）。
3.结束条件：也就是到达决策树底层（叶子节点），无法再做选择的条件。

回溯算法的框架

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
result = []
def backtrack(路径, 选择列表):
    # 出口
    if 满足结束条件:
        result.add(路径)
        return
    
    for 选择 in 选择列表:
        # 做选择
        # 将该选择从选择列表中移除
        路径.add(选择)
        backtrack(路径,选择列表)
        # 撤销选择
        # 将该选择恢复到选择列表
        路径.remove(选择)

注：

  • 做选择的就是将选择列表中的选择放入路径中，作为一个已经选择过的路径。
  • 撤销选择的原因是当for循环遍历所有选择时，做完一个选择后，下一个选择还是基于上一个选择的，所以要恢复原来的(路径，选择列表)，即回到上一个节点，本质其实就是DFS。