leetcode-Backtracking

回溯算法

回溯算法可以解决的问题

  • 组合问题：N个数里面按一定规则找出k个数的集合
  • 切割问题：一个字符串按一定规则有几种切割方式
  • 子集问题：一个N个数的集合里有多少符合条件的子集
  • 排列问题：N个数按一定规则全排列，有几种排列方式
  • 棋盘问题：N皇后，解数独等等

回溯法一般都可以抽象为树形结构，解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度就构成了树的深度。

  1. 确定回溯函数模板返回值以及参数
  2. 确定回溯函数终止条件
  3. 确定
  4. 回溯搜索的遍历过程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def backtracking(参数):
    if 终止条件:
        存放结果;
        return;
    
    for 选择 in 当前节点的邻居:  # 本节点所连接的其他节点
        处理节点;
        backtracking(路径，选择列表); // 递归
        回溯，撤销处理结果

def backtracking(parameters):
    if termination_condition:
        # store_result
        return

    for choice in current_layer_choices:
        process_node(choice) # process choice
        backtracking(path, choices_list)  # Recursion
        undo_process_node(choice)  # Backtrack