回溯法讲解（结合图和案例）

一、简述

回溯法，以穷举的形式，对问题有可能出现的解罗列出来，必要的时候会包含剪枝的操作。根据罗列的形式不一样，又有分为两种：

• 子集树 回溯

• 排列树 回溯

二、步骤

1. 根据题目，找到相应解空间，即解可能的组合
2. 选择相应的解空间树（子集 or 排列），这一步最好画出来，便于理解分析
3. 使用深度优先搜索（dfs）搜索树（必要的时候带上剪枝）

如上，因为第 3 步可以直接套用 三、解题模型，因此重要的一步便是 2，选择什么样的结构去解决题目，那么该如何确定选择哪种结构呢？如下分析：

• 子集树：从给出集合中，找出满足某些条件的子集。
  如： 01 背包问题，就是从物品集合中，找出最大重量的子组合、

• 排列树：将集合中的元素，给出按照某些条件进行排列的子集
  如：排列数字，就是将集合（{1, 2, 3}）进行排序，给出所有可能的排序。

三、解题模型

由于树的搜索（这里是 dfs）可以选用栈或者递归的方式，因此也有两种模型

1. 栈

pass，持续更新后补

2. 递归（常用）

使用递归的方式进行通解，通常要定义如下参数：

• int k - 当前层
• int n - 总层数 （如果总层数使用解的个数，则无需定义）
• vector<T>& x - 解
• vector<T>& res - 记录的结果

以及剪枝函数（有时候也叫限界函数）：

• constraint(k) 即判断是否有必要进行下一次的hui's

2.1 子集树

void backtrack(int k, vector<T>& x, vector<T>& res) {

  if (k >= x.size()) {
      // 此处做记录
      res.push_back(x);
  } else {
      // 继续深入
      for (int i=0; i<=1; i++) {
          x[t] = i; // 选 0 或者 1

          if (constraint(k)) {
               backtrack(k+1, x, res);
          }
      }
  }

}

2.2 排列树

void backtrack(int k, vector<T>& x, vector<T>& res) {

  if (k >= x.size()) {
      // 此处做记录
      res.push_back(x);
  } else {
      // 继续深入
      for (int i=k; i<=x.size(); i++) {
          
          swap(x[t], x[i]);
          if (constraint(k)) {
               backtrack(k+1, x, res);
               swap(x[t], x[i]);
          }
      }
  }

}

排列树主要是通过 swap(a: T, b: T) 方法对元素交叉排列，在结束之后再交换回来（恢复状态）。

四、案例

TODO 持续更新