回溯算法

如何理解回溯算法

回溯法解决的问题都可以抽象为树形结构。

因为回溯法解决的都是在集合中递归查找子集，集合的大小就构成了树的宽度，递归的深度，都构成的树的深度。

递归就要有终止条件，所以必然是一棵高度有限的树（N叉树）。

换句话来说，回溯其实是一种暴力搜索的算法，他用递归来控制for循环的

回溯法模版

• 回溯函数的返回值及参数

回溯算法中函数返回值一般为void。

回溯算法需要的参数可不像二叉树递归的时候那么容易一次性确定下来，所以一般是先写逻辑，然后需要什么参数，就填什么参数。

但是卡哥给我们讲题的时候肯定会一开始就帮我们把参数确定下来。

回溯函数伪代码

void backtracking(参数)

• 回溯函数终止条件

既然回溯问题可以抽象成树形结构，那么遍历树形结构一定要有终止条件，所以回溯也要有终止条件。

什么时候达到了终止条件，树中就可以看出，一般来说搜到叶子节点了，也就找到了满足条件的一条答案，把这个答案存放起来，并结束本层递归。

if (终止条件)
{
  收集结果;
  return;
}

• 回溯搜索的遍历过程

在上面我们提到了，回溯法一般是在集合中递归搜索，集合的大小构成了树的宽度，递归的深度构成的树的深度。

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

大家可以从图中看出for循环可以理解是横向遍历，backtracking（递归）就是纵向遍历，这样就把这棵树全遍历完了，一般来说，搜索叶子节点就是找的其中一个结果了。

回溯算法模版框架

void backtracking(参数) {
    if (终止条件) {
        存放结果;
        return;
    }

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

77.组合

力扣题目链接

文章讲解：77.组合

视频讲解：带你学透回溯算法-组合问题（对应力扣题目：77.组合），组合问题的剪枝操作

状态：需要把组合问题展示成属性结构来进行组合的配对

树形结构

我们一定要把问题抽象成树形结构。

给他画一个回溯算法的搜索过程。我们可以抽象成如下树形结构

对于每一组都只取后面的数，防止重复

回溯三部曲

如何使用代码来实现呢？这里就要用到我们的回溯三部曲：

• 复习一下之前讲的回溯模板框架

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

• 回溯三部曲：回溯算法相当于递归里面嵌套for循环

  • 递归函数的参数和返回值：因为回溯就是靠递归来实现的，所以我们称这个函数是递归函数
  • 确定递归函数的终止条件
  • 确定单层递归的逻辑，也就是单层递归的逻辑

下面按照回溯三部曲，对照着树形结构给出伪代码

伪代码

• 递归函数的参数和返回值：
  • 返回值一般都是void
  • 由于题目要求一个组合，所以我们定义一个一维数组来存放遍历的路径path（因为我们的路径就是结果）；然后定义一个result来存放各个路径的集合；但是在本题中，我们将这两个定义为全局变量，免得函数参数过多，影响可读性。
  • 关于参数startIndex的强调：**我们每次递归的时候会把我们这次要搜索的其实位置传进来。**一层递归结束之后，我们在下一层递归，为了防止重复组合的出现，我们要定义好从哪开始。比如说[1, 2, 3, 4]我们把1的组合搜索光了，开始搜索2的组合时，我们应该从3开始搜索以构成[2, 3]

void backtracking(n, k, startIndex){	//n表示几个数，k表示组合的大小，startIndex
  
}

• 确定终止条件：到了叶子结点我们要收集我们想要的结果

if (path.size == k){	//我们的path收集到k个数了，存入一次结果
  result.push(path);
  return;
}

• 单层搜索的逻辑：每一个结点其实都是一个for循环，for循环的起始位置就是从startIndex开始，然后遍历剩余的元素。

for (i=startIndex; i <= n; i++){
  path.push(i);	//遍历完一个结点
  backtracking(n, k, ++i);
  path.pop();
}

CPP代码实现

class Solution{
private:
  vecotr<vector<int>> result;	//存放符合条件结果的集合
  vector<int> path;	//用来存放符合条件结果
  void backtracking(int n, int k, int startIndex){
    if (path.size() == k) {
      result.push_back(path);
      return;
    }
    for (int i = startIndex; i <= n; i ++){
      path.push_back(i);	//处理结点
      backracking(n, k, i + 1);	//递归
      path.pop_back();	//回溯， 撤销处理的结点
    }
  }
public:
  vector<vector<int>> combine(int n, int k){
    result.clear();
    path.clear();
    backtracking(n, k, 1);
    return result;
  }
}

组合问题的剪枝操作

组合问题的剪枝操作**
拿77题举例：组合问题

如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。

所以我们这里主要瞄准的问题，就是for循环里选择的起始位置：

for (int i = startIndex; i <= n; i++){

优化过程如下：

1. 已经选择的元素个数：path.size()
2. 所需需要的元素个数为：k - path.size()
3. 列表中剩余元素n - i >= 所需需要的元素个数 (k - path.size())
4. 在集合中至多要从该起始位置开始遍历：i <= n - (k - path.size()) + 1

这里为什么要加1呢？包头包尾，其实就是左闭区间

举个例子，n = 4，k = 3， 目前已经选取的元素为0（path.size为0），n - (k - 0) + 1 即 4 - ( 3 - 0) + 1 = 2。

从2开始搜索都是合理的，可以是组合[2, 3, 4]。

所以说for循环是：

for (int i = startIndex; i <= n - (k - path.size()) + 1; i++) // i为本次搜索的起始位置