回溯法，一般可以解决如下几种问题，都可以化成选择树,递归用来纵向遍历，for循环用来横向遍历:

  • 组合问题：N个数里面按一定规则找出k个数的集合
  • 切割问题：一个字符串按一定规则有几种切割方式->转化为组合问题
  • 子集问题：一个N个数的集合里有多少符合条件的子集（收集树的所有节点）
  • 排列问题：N个数按一定规则全排列，有几种排列方式
  • 棋盘问题：N皇后，解数独等等
  • 其他分步组合问题

是一种暴力的穷举方法。

模板

注意：for循环外部，每一层函数的递归，代表树的一层（路径长度都为2的子集…） for循环内部代表这一个节点的不同分支

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
void backtracking(路径, 选择列表) {
    if (终止条件) {
        存放结果;
        return;
    }

    // 做选择
    //printf("我在 %s 节点上做选择", root);

    
     for 选择 in 选择列表{
        
        // 剪枝逻辑
        if (...) {
            // 第 i 个选择不满足条件则跳过
            continue;
        }
        
        
        处理节点;
        
        // 做选择
        //printf("我在 %s 和 %s 中间的树枝上做选择", root, child);
        
        backtracking(路径，选择列表); // 递归

        // 撤销选择
        //printf("我在 %s 和 %s 中间的树枝上撤销选择", root, child);
        
        回溯，撤销处理结果
    }

  // 撤销选择
  //  printf("我在 %s 节点上撤销选择", root);

}

排列/组合子集问题

组合问题和子集问题等价
常用剪枝：

  • used数组（排列问题）
  • startIndex（组合/子集问题，保证元素 nums[start] 之后只会出现 nums[start+1..] 中的元素，通过固定元素的相对位置保证不出现重复的子集。）
    1. 子集 II [1,2,2]-> [[],[1],[1,2],[1,2,2],[2],[2,2]]
      需要先排序，一个节点有多条值相同的树枝相邻，则只遍历第一条，剩下的都剪掉，不要去遍历.
      如果发现 nums[i] == nums[i-1]，则跳过（保证同一树层相同元素只会被使用一次）
    1. 全排列 II [1,1,2] -> [[1,1,2],[1,2,1],[2,1,1]]
      需要先排序，一个节点有多条值相同的树枝相邻，则只遍历第一条，剩下的都剪掉，不要去遍历.
      一种剪枝：因为排序之后所有相等的元素都挨在一起，所以只要用 prevNum 记录前一条树枝的值，就可以避免遍历值相同的树枝，从而避免产生相同的子树，最终避免出现重复的排列。

数独、N皇后

这道题可以认为是数独游戏和 N 皇后问题的简化版：
这道题相当于让你对一个长度为 n 的一维数组中的每一个位置进行穷举，其中每个位置可以填 0 或 1。

数独游戏相当于让你对一个 9x9 的二维数组中的每个位置进行穷举，其中每个位置可以是数字 1~9，且同一行、同一列和同一个 3x3 的九宫格内数字不能重复。

N 皇后问题相当于让你对一个 N x N 的二维数组中的每个位置进行穷举，其中每个位置可以不放皇后或者放置皇后（相当于 0 或 1），且不能存在多个皇后在同一行、同一列或同一对角线上。