DFS 与回溯：沿一条路径做完选择再撤销｜算法讲义

解决什么问题#

深度优先搜索（DFS）适合探索由连续选择构成的状态空间：先沿一条路径走到终点，再退回最近的分叉点尝试其他选择。回溯是在 DFS 上维护“当前方案”的写法，常用于：

生成排列、组合和子集；
棋盘放置、数独等约束满足问题；
在图或树中遍历连通结构；
寻找一条满足条件的路径，或统计全部方案。

当解本身是一串选择时，回溯通常比复制整个状态更自然：进入下一层前修改状态，返回后再恢复。

核心思想与不变量#

一个回溯函数通常包含四部分：

定义当前递归参数表达的状态；
判断是否已经得到完整答案；
枚举当前状态可做的选择；
做选择、递归、撤销选择。

模板生成从 1..n 中选出 $k$ 个数的全部组合。进入 dfs(next) 时保持两个不变量：

path 严格递增，且只包含已经选择的合法数字；
小于 next 且不在 path 末端之后的数字不会再被选择，因此每个组合只生成一次。

如果剩余数字数量小于还需要选择的数量，这条分支不可能完成，可以直接剪掉。循环上界 n - need + 1 正是把这个剪枝提前写进候选范围。

复杂度#

一般搜索树若深度为 $d$ 、每层最多有 $b$ 个分支，最坏时间为 $O(b^d)$ ，递归栈和当前路径占 $O(d)$ 空间。

生成所有 $k$ 组合时，答案本身有 $\binom{n}{k}$ 个，每个答案需要复制 $k$ 个元素，因此时间至少是 $\Omega(k\binom{n}{k})$ 。模板借助剪枝只访问有希望完成的前缀，空间除输出外为 $O(k)$ 。

C++17 模板：生成固定大小组合#

#include <iostream>
#include <stdexcept>
#include <vector>

class CombinationGenerator {
 public:
  std::vector<std::vector<int>> generate(int n, int k) {
    if (n < 0 || k < 0 || k > n) {
      throw std::invalid_argument("require 0 <= k <= n");
    }
    n_ = n;
    k_ = k;
    path_.clear();
    answers_.clear();
    dfs(1);
    return answers_;
  }

 private:
  int n_ = 0;
  int k_ = 0;
  std::vector<int> path_;
  std::vector<std::vector<int>> answers_;

  void dfs(int next) {
    if (static_cast<int>(path_.size()) == k_) {
      answers_.push_back(path_);
      return;
    }

    const int need = k_ - static_cast<int>(path_.size());
    // value 再大就凑不齐 need 个数，因此缩短循环范围。
    const int last_candidate = n_ - need + 1;

    for (int value = next; value <= last_candidate; ++value) {
      path_.push_back(value);  // 做选择
      dfs(value + 1);
      path_.pop_back();        // 撤销选择，恢复进入本轮前的状态
    }
  }
};

int main() {
  CombinationGenerator generator;
  const auto combinations = generator.generate(4, 2);

  for (const auto& combination : combinations) {
    for (int value : combination) {
      std::cout << value << ' ';
    }
    std::cout << '\n';
  }
}

C++17 模板：图遍历与网格连通块#

图 DFS 与回溯共用递归框架，但状态恢复方式不同：普通连通性遍历中，一个顶点一旦访问就保持已访问，不在返回时撤销；网格 DFS 则把上下左右移动看作隐式图的四条候选边。

下面同一份程序给出邻接表遍历和网格连通块面积两个接口。graph_dfs_order 返回从起点可达节点的 DFS 顺序；grid_component_size 返回起点所在 . 连通块的格子数。

#include <iostream>
#include <stdexcept>
#include <string>
#include <vector>

void dfs_graph(int vertex, const std::vector<std::vector<int>>& graph,
               std::vector<bool>& visited, std::vector<int>& order) {
  visited[vertex] = true;  // 进入节点时标记，避免沿环再次递归。
  order.push_back(vertex);

  for (int next : graph[vertex]) {
    if (next < 0 || next >= static_cast<int>(graph.size())) {
      throw std::out_of_range("an edge endpoint is outside the graph");
    }
    if (!visited[next]) {
      dfs_graph(next, graph, visited, order);
    }
  }
}

std::vector<int> graph_dfs_order(
    const std::vector<std::vector<int>>& graph, int source) {
  if (source < 0 || source >= static_cast<int>(graph.size())) {
    throw std::out_of_range("source is outside the graph");
  }
  std::vector<bool> visited(graph.size(), false);
  std::vector<int> order;
  dfs_graph(source, graph, visited, order);
  return order;
}

int dfs_grid(const std::vector<std::string>& grid, int row, int column,
             std::vector<std::vector<bool>>& visited) {
  const int rows = static_cast<int>(grid.size());
  const int columns = static_cast<int>(grid[0].size());
  if (row < 0 || row >= rows || column < 0 || column >= columns ||
      grid[row][column] == '#' || visited[row][column]) {
    return 0;
  }

  visited[row][column] = true;
  int size = 1;
  constexpr int directions[4][2]{{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
  for (const auto& direction : directions) {
    size += dfs_grid(grid, row + direction[0], column + direction[1],
                     visited);
  }
  return size;
}

int grid_component_size(const std::vector<std::string>& grid,
                        int start_row, int start_column) {
  if (grid.empty() || grid[0].empty()) {
    return 0;
  }
  const std::size_t columns = grid[0].size();
  for (const std::string& row : grid) {
    if (row.size() != columns) {
      throw std::invalid_argument("grid must be rectangular");
    }
  }
  std::vector<std::vector<bool>> visited(
      grid.size(), std::vector<bool>(columns, false));
  return dfs_grid(grid, start_row, start_column, visited);
}

int main() {
  const std::vector<std::vector<int>> graph{{1, 2}, {0, 3}, {0}, {1}};
  const std::vector<int> order = graph_dfs_order(graph, 0);
  std::cout << "graph order:";
  for (int vertex : order) {
    std::cout << ' ' << vertex;
  }

  const std::vector<std::string> grid{"..#.", ".##.", "...."};
  std::cout << "\ncomponent size = " << grid_component_size(grid, 0, 0)
            << '\n';
}

邻接表 DFS 的时间为 $O(V+E)$ 、辅助空间为 $O(V)$ ；网格中每个可达格子至多进入一次，时间和访问数组均为 $O(RC)$ 。递归深度在链式图或巨大连通块上可能达到节点数，此时应改用显式栈。

示例推演#

令 $n=4,k=2$ 。搜索首先选择 1，路径变化如下：

[] → [1] → [1, 2]  输出
          → [1, 3]  输出
          → [1, 4]  输出
   → [2] → [2, 3]  输出
          → [2, 4]  输出
   → [3] → [3, 4]  输出

根节点不会从 4 开始，因为只剩一个数字，不可能再凑出两个元素。这就是基于“剩余容量”的剪枝。

易错点#

递归后忘记 pop_back()，使兄弟分支继承了不属于自己的选择。
没有清楚定义参数语义，例如混淆“当前下标”和“下一候选下标”。
组合问题每层都从 1 开始，导致重复答案；排列问题却错误地使用递增起点，漏掉合法顺序。
在图 DFS 中只在返回时标记访问，遇到环会无限递归。图遍历通常应在进入节点时标记。
使用全局容器多次求解，却没有在新一轮开始前清空。
剪枝只凭直觉，没有证明被剪分支不可能包含答案。