回溯算法

回溯算法可以处理的问题

  • 组合
  • 分割
  • 子集
  • 排列
  • 棋盘

回溯算法推理模板

画一棵树，横向代表每一次for循环，纵向代表递归深度。

回溯算法模板

1
2
3
4
5
6
7
8
9
10
11
12
void backtracking(参数){
    if(终止条件){
        存放结果
        return;
    }

    for(选择本层集合元素){
        处理节点
        backtracking() 递归
        回溯，撤销处理操作
    }
}

注意事项

  • 递归传递startIndex参数时，要使用(i+1)的形式（++i/i++都会实际改变i的值，且i++的运算在传参之后）