回溯法思考模板：

    1. void tracebacking(参数){
    2.   if(终止条件){
    3.     存放结果;
    4.     return;
    5.    }
    7.   for(选择：本层集合元素(树中节点孩子数量就是集合的大小)){
    8.     处理节点;
    9.     tracebacking(路径,选择列表);
    10.     回溯，撤销处理结果;
    11.    }
    12. }

    回溯过程可以处理为树形结构，每一层集合元素是树的宽度，递归次数是树的深度。
    回溯法用递归解决嵌套层数的问题，例如：组合问题！在这道题中如果层数过大，根本无法用for循环来解决，此时，应当考虑回溯，递归的每一层就是每一层的for循环。每次从集合中选取元素，可选择的范围随着选择的进行而收缩，调整可选择的范围。变式：组合总和。
    注意：如何进行剪枝是回溯法使用过程中的难题，所以我们可以画出树形图，在图形上分析剪枝就会容易很多。

    对于组合问题，什么时候用startIndex，什么时候不用：如果是用一个集合求组合，就需要用startIndex 如：组合总和，如果是多个集合取组合，各个集合之间不影响，就不用startIndex 如：电话号码的字母组合。
    对于重复元素求组合问题，先排序再求，要用startIndex。如 ：组合问题

    数组中存在重复元素，但是所求组合中不能出现重复答案，这种组合问题应该如何处理：例题
    这种情况我们要去除的是在同一树层上使用过的元素，在同一树支上的重复元素可以保留。设置一个used数组，初始化为0，如果

    1. nums[i- 1] == nums[i] && used[i - 1] == 0 
    2. //这就是在同一层出现过的元素，直接跳过
    3. nums[i- 1] == nums[i] && used[i - 1] == 1
    4. //这就是在一条树支上出现过的元素

    树层去重，必须对数组进行排序。
    此题我也写了如何直接用startIndex进行去重的方法：
    主要回溯逻辑模块：

    1. for (int i = startIndex; i < candidates.size() && target - candidates[i] >= 0; i++) {
    2.     if(i > startIndex && candidates[i] == candidates[i - 1]){
    3.         continue;
    4.     } 
    5.     target -= candidates[i];
    6.     path.push_back(candidates[i]);
    7.     traceBacking(candidates, i + 1, target);
    8.     path.pop_back();
    9.     target += candidates[i];
    10. }

    因为是要对同一树层进行去重，而不是树支，当i > startIndex时，它开始往层走。此时去掉一致的元素。

    字符串问题的回溯解法：分割回文串
    逻辑图：
    903E62ED0F5300C3316FF69C87646C84.jpg
    当出现不满足条件的情况时，不再递归，但是横向还要进行，横向找到满足的后要继续递归：（递归过程放在条件以外的原因）。
    6E797D6EC29BEDE342D5739F019A423C.jpg
    回溯核心代码部分：

    1. for (int i = startIndex; i < s.size(); i++) {
    2.     if(pralindrome(s,startIndex,i)) {
    3.         string str = s.substr(startIndex, i - startIndex + 1);
    4.         path.push_back(str);
    5.     }
    6.     else {
    7.         continue;//不满足的时候横向继续
    8.     }
    9.     traceBacking(i + 1,s);//只有满足条件才继续纵向递归
    10.     path.pop_back();
    11. }

    接下来看这道题的对比版：复原IP地址
    这道题和上一道题都是满足条件时才继续递归，但是这道题不满足条件时，横向永远也无法满足条件，所以只能跳过。所以递归过程要放在满足条件的括号以内。
    5B99003C0E6A8DFBA5682E003A75D81A.jpg

    1. for (int i = startIndex; i < s.size(); i++) {
    2.     if(isValid(s, startIndex, i)) {
    3.         s.insert(s.begin() + i + 1, '.');
    4.         pointNum++;
    5.         traceBacking(s,i + 2, pointNum);
    6.         pointNum--;
    7.         s.erase(s.begin() + i + 1);
    8.     }
    9.     else {
    10.         break;
    11.     }
    12. }

    这种字符串相关的回溯题目如果理解不清楚，一定要先画出递归树，根据递归树来确定横向和纵向，想是想不清楚的。

    求子集问题，求子集问题和组合问题的区别在于：子集问题是求树的每一个结点，但是组合问题是求树的叶子结点。
    FD370A6628D5346F7F3FC421A1A9C2DA.jpg
    子集问题+去重：注意此处树层去重的条件，并且树层去重，需要先排序—>方便通过相邻的结点判断是否重复使用过。

    递增子序列问题： 首先明确这是一个求任意深度大于1的结点问题，并且数组已经预先给好，不能排序，所以需要在每一层判断当前元素是否已经出现过。可以使用在每一层使用一个set数组来判断，注意在每一层定义：
    52579882651A6D58DB20AE3BC9BAEA26.jpg

    注意区分子集问题+去重 和 递增子序列问题：这两道题的区别递增子序列的去重是在同一父节点的，而子集问题加去重是在整棵树的本层，所以我们要先排序来判断去重。
    排列问题：首先排列问题一定是求叶子结点的问题
    31790962B65BC46F3E73A812B3379B59.jpg
    因为排列问题，每次都要从头开始搜索，例如1在[1，2]中出现过了，后面[2,1]中会再出现一次，所以不需要startIndex，但是需要一个used[]记录此时路径中哪些数已经被使用过了。全排列
    全排列去重问题：注意树层去重的逻辑。