回溯

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。
回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。

回溯的思路

当前局面下，我们有若干种选择，所以我们对每一种选择进行尝试。如果发现某种选择违反了某些限定条件，此时 return；如果尝试某种选择到了最后，发现该选择是正确解，那么就将其加入到解集中。
在这种思想下，我们需要清晰的找出三个要素：选择 (Options)，限制 (Restraints)，结束条件 (Termination)。
终止时一层一层的向上返回，递归有一定的深度。

回溯类型问题

  1. 组合
  2. 切割
  3. 子集
  4. 排列

  5. 棋盘（N皇后，解数独）

    代码模板

    一般有两部分组成
    停止条件（返回）
    循环（添加元素，回溯，回溯后操作（撤销处理节点的情况）)

    1. void backtracking(参数){
    2.  if(终止条件){
    3.      收集结果
    4.      return;
    5.  }
    7.  for(集合元素集){
    8.      处理节点
    9.      递归函数
    10.      回溯操作（撤销处理节点的情况）
    11.  }
    12. }

    例题

  6. 括号生成

  7. 组合
    78. 子集
    79. 单词搜索

    参考资料