back_tracking.md

Table of Contents generated with DocToc

• 回溯法（back tracking）
  • 分类

回溯法（back tracking）

是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择， 这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点.

dfs(i)-->dfs(i+1) 注意：参数 i 的含义不是第 i 个，而是 >= i 的部分

分类

电话号码的字母组合

1. 子集型回溯

站在输入的视角: 每个元素选或不选 站在答案的视角：每个节点都是答案

• 相同案例：分割回文串

2. 组合型回溯：可以减枝优化

假设遍历路径 path 长度为 m, 那么还需要查找 d=k-m 个数。如果是从[1,i]倒序这i个数中选数，如果i<d,那么肯定选不出k个数，直接return,这就是剪枝。

组合总和 III

括号生成

 

dfs[i,open]

• dfs[i+1,open+1] 选左括号
• dfs[i+1,open] 选右括号

3. 排列型回溯

全排列