回溯法
来自智得网
简介
回溯法是一种选优搜索法，在回溯过程中按选优条件向前搜索或者试探，以达到目标结果。但当探索到某一步时，发现之前的选择路径不能达成目标或者不是最优的方案，就沿着已经选择的路径进行回退重新选择，这种按照一定规则试探，并且试探失败就回退到一定状态重新试探的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
流程
回溯法解决的典型问题一般分为三类，分别是子集问题，组合问题，以及排列问题。
解决一个回溯问题，实际上就是一个决策树的遍历过程。一般情况下分为三步：
确定试探路径，也就是之前试探中的选择集合。
确定当前的选择条件，当前可以进行选择的选择列表。
结束条件是值到达决策树底层，可以结束本次回溯的条件。
回溯法流程的通用模版可以抽象如下：
回溯(路径, 选择列表){
如果到达终止条件：
将该路径加入结果列表；
循环选择列表:
#将该选择添加到选择路径
路径.添加(选择)
回溯(路径, 选择列表)
# 撤销选择
路径.删除(选择）
}
示例
子集问题
给定一个数组，返回它所有的子集。如nums=[1, 2, 3] 返回的是[[],[1],[1,2],[1,2,3],[1,3],[2],[2,3],[3]]。
集合中有有三个数组，每次从集合中可能选择的有4个值，分别是1、2、3和空。
返回4个可选值集合所有的子集，试探路径最长为4。
所以当路径长度为4时，则将该路径存入结果集中。