回溯算法

回溯模板

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
    处理节点;
    backtracking(路径，选择列表); // 递归
    回溯，撤销处理结果
	}
}

例1：77. 组合

参数：begin代表用来记录本层每个节点递归的中，集合从哪里开始遍历（集合就是[1,...,n] ）

n相当于树的宽度，k相当于树的深度

这个参数解决的问题就是选过元素还需不需要选，结合全排列问题考虑

for (int i = startIndex; i <= n; i++) { // 控制树的横向遍历
    path.push_back(i); // 处理节点 
    backtracking(n, k, i + 1); // 递归：控制树的纵向遍历，注意下一层搜索要从i+1开始
    path.pop_back(); // 回溯，撤销处理的节点
}

本题元素不能重复被选取，故要i+1。注意与例2的区别.

回溯法的搜索过程就是一个树型结构的遍历过程，在如下图中，可以看出for循环用来横向遍历，递归的过程是纵向遍历。

例2：39. 组合总和

题还需要startIndex来控制for循环的起始位置，对于组合问题，什么时候需要startIndex呢？

• 如果是一个集合来求组合的话，就需要startIndex，例如：77.组合 (opens new window)，216.组合总和III (opens new window)。

• 如果是多个集合取组合，各个集合之间相互不影响，那么就不用startIndex，例如：17.电话号码的字母组合(opens new window)

注意以上我只是说求组合的情况，如果是排列问题，又是另一套分析的套路，后面我再讲解排列的时候就重点介绍。

本题和77组合,216组合总和III的区别：本题元素可以重复选取，所以关键代码逻辑如下：

for (int i = begin; i < candidates.size(); i++) {
    sum += candidates[i];
    path.push_back(candidates[i]);
    backtracking(candidates, target, sum, i); // 关键点:不用i+1了，表示可以重复读取当前的数
    sum -= candidates[i];   // 回溯
    path.pop_back();        // 回溯
}

注意递归函数中的参数是i而不是i+1。用递归是纵向遍历来理解，递归遍历的是遍历”树的枝“，循环遍历的是‘’树的层“。

例3：40. 组合总和 II

来自代码随想录的解析理解

这道题目和例2的组合总和 如下区别：

1. 本题candidates 中的每个数字在每个组合中只能使用一次。
2. 本题数组candidates的元素是有重复的，而39.组合总和 (opens new window)是无重复元素的数组candidates。

最后本题和39.组合总和 (opens new window)要求一样，解集不能包含重复的组合。

这里有一个难点就是去重问题：

组合问题可以抽象为树形结构，那么“使用过”在这个树形结构上是有两个维度的，一个维度是同一树枝上使用过，一个维度是同一树层上使用过。

那么问题来了，我们是要同一树层上使用过，还是同一树枝上使用过呢？

回看一下题目，元素在同一个组合内是可以重复的，怎么重复都没事，但两个组合不能相同。

所以我们要去重的是同一树层上的“使用过”，同一树枝上的都是一个组合里的元素，不用去重。

此题还需要加一个bool型数组used，用来记录同一树枝上的元素是否使用过。这个集合去重的重任就是used来完成的。(后面还有一个不用加used数组的方法理解)

接下来的问题就是如何判断同一个树层上元素(相同的元素)是否使用过？

如果candidates[i] == candidates[i - 1] 并且 used[i - 1] == false，就说明：前一个树枝，使用了candidates[i - 1]，也就是说同一树层使用过candidates[i - 1]。

此时for循环里就应该做continue的操作。

used[i-1]==false触发判断的前提条件是candidates[i] == candidates[i - 1],其余看蓝色字体部分的理解。

for (int i = startIndex; i < candidates.size() && sum + candidates[i] <= target; i++) {
    // used[i - 1] == true，说明同一树枝candidates[i - 1]使用过
    // used[i - 1] == false，说明同一树层candidates[i - 1]使用过
    // 要对同一树层使用过的元素进行跳过
    if (i > 0 && candidates[i] == candidates[i - 1] && used[i - 1] == false) {
        continue;
    }
    //做出选择
    ····
     backtracking(candidates, target, sum, i + 1, used); // 和39.组合总和的区别1：这里是i+1，每个数字在每个组合中只能使用一次
    ····
    //撤销选择
}

不用used数组的方法：

if (i > begin && candidates[i] == candidates[i - 1])                
	continue;            

i>begin的解释: (比较难理解)

例4：17. 电话号码的字母组合

这题和上面的组合题不同之处在于它是在不同集合里面取元素，所以我们使用一个depth表示：每次递归都从不同数字映射出的元素去取。例如上图所示：当depth=0时，我们从数字‘2’映射出来的”abc“取，然后递归纵向遍历depth+1,我们从数字‘3’映射出来的“def”取。

for(int i=0;i<str.length();i++){//这里是i=0,不是i=depth,从不同集合取进行组合,for循环横向遍历,每次都从新集合里面从第一个开始取。
       temp.append(str.charAt(i));
       trackback(digits,numString,depth+1);//这里是depth+1,不是i+1,递归纵向遍历，depth+1取下一个集合的元素
       temp.deleteCharAt(temp.length()-1);
}

例5：131. 分割回文串

难点就是如何切割并且画出递归树。

for(int i=begin;i<s.length();i++){
            String subString=s.substring(begin,i+1);//substring()是切割字符串的左闭右开区间，所以要i+1.
            if(!ishuiwenString(subString))//如果不是回文字符串则跳过
                continue;
            path.add(subString);
            backtrack(s,i+1);//这里i+1是同一个位置不能重复切割,递归纵向遍历在下一位置进行切割
            path.removeLast();
        }

begin代表切割线,[begin,i]就是要截取的子串

例6：78. 子集

子集问题与组合和切割问题的区别：在树形结构中子集问题是要收集所有节点的结果，而组合问题是收集叶子节点的结果。

void backtracking(vector<int>& nums, int startIndex) {
        result.push_back(path); // 收集子集，要放在终止添加的上面，否则会漏掉自己
        if (startIndex >= nums.size()) { // 终止条件可以不加
            return;
        }
        for (int i = startIndex; i < nums.size(); i++) {
            path.push_back(nums[i]);
            backtracking(nums, i + 1);
            path.pop_back();
        }
    }

例7：90. 子集 II

那么关于回溯算法中的去重问题，在40.组合总和II (opens new window)中已经详细讲解过了，和本题是一个套路

多加一个used数组即可。

例8：491.递增子序列

本题的由于题目要求的原因不能对原数组进行排序，所以无法使用前面去重的方法进行去重，本题使用哈希数组来进行去重。

​ 同一父节点下的同层上使用过的元素就不能在使用了

int[] used = new int[201];// 这里使用数组来进行去重操作，题目说数值范围[-100, 100]
//这里used数组的创建是在for循环外，而不是在for循环内！
for (int i = start; i < nums.length; i++) {
     if (!path.isEmpty() && nums[i] < path.get(path.size() - 1) ||(used[nums[i] + 100] == 1)) 
         continue;
      used[nums[i] + 100] = 1;// 记录这个元素在本层用过了，本层同一个父节点后面不能再用了
      path.add(nums[i]);
      backtracking(nums, i + 1);
      path.remove(path.size() - 1);
}