基本理论

  • 回溯算法和递归是相辅相成的
  • 回溯法是一种纯暴力的算法,它并不是高效算法.
  • 回溯问题都可以抽象成树形结构.

回溯法可以解决哪些问题?

  • 组合问题: 在一组数据中找到大小为2的组合.
  • 切割问题: 给一个字符串,有几种切割方式.
  • 子集问题
  • 排列问题: 排列强调顺序,组合不强调问题
  • 棋盘问题: N皇后

回溯法的模板

  • 递归函数一般没有返回值.
  • 递归函数的命名一般叫backtracking(参数)
  • 需要有终止条件,在终止条件内收集结果.
1
2
3
4
5
6
7
8
9
10
11
12
void basetracking(参数){
    if(终止条件){
        收集结果
        return;
    }

    for(集合元素){
        处理节点;
        递归函数;
        回溯操作;
    }
}

力扣22题, 括号生成

组合问题

回溯问题可以通过递归的方式控制for循环的嵌套层数

剪枝操作

for(集合元素) 通过某种判断条件减少遍历次数