普通深度优先搜索¶

分解数字

给定一个正整数 \(n\)，要你分解成 \(3\) 个正整数，要求排在后面的数要比前面的数要大。输出所有的方案。

一看题目，诶，这不是非常简单吗？直接用我们之前在枚举章节里面学习到的暴力枚举法枚举三个数不就行了？

暴力枚举

for (int i = 1; i <= n; i++) {
  for (int j = i; j <= n; j++) {
    for (int k = j; k <= n; k++) {
      if (i + j + k == n) {
        cout << i << ' ' << j << ' ' << k << '\n';
      }
    }
  }
}

可是，要是这道题不是分解成 \(3\) 个数，而是分解成 \(4\) 个，\(5\) 个，甚至 \(m\) 个呢？难道真的要写 \(m\) 层循环吗？这时候，普通的循环显然无法满足了，就需要进行递归搜索。

我们就把整个状态分为 \(m\) 层，第 \(i\) 层的状态由 \((i,x,v)\) 来表示，表示当前正在选择第 \(i\) 个数，前面的数累加起来的和已经达到了 \(x\)，搜索的序列为 \(v\)。那么我们就从 \(v\) 的最后一个元素开始枚举，然后不停地递归搜索，直到 \(i\) 大于 \(m\) 并且 \(x\) 正好等于 \(n\)，就说明我们已经成功搜到了一个合法的解，那么就输出答案并退出搜索搜索。

代码

void dfs(int i, int x, vector<int> v) {
  if (i > m) {
    if (x > n) {
      for (int j : v) {
        cout << j << ' ';
      }
      cout << '\n';
    }
    return;
  }
  for (int j = v.back(); j <= n; j++) {
    v.push_back(j);
    dfs(i + 1, x + j, v);
    v.pop_back();
  }
}

然后我们会发现，其实在搜的过程中，我们并不需要记录整个 \(v\) 放在状态当中，而是使用一个全局变量，因为深度优先搜索（代码的搜索方法）不会改变状态的前继，形象一点就是我们是直接搜到 \(i>m\) 之后才退出的，因此可以使用全局变量记录路径。

代码

void dfs(int i, int x) {
  if (i > m) {
    if (x == n) {
      for (int j = 1; j <= m; j++) {
        cout << a[j] << '\n';
      }
      cout << '\n';
    }
    return;
  }
  for (int j = i == 1 ? 1 : a[i - 1]; j <= 1; j++) {
    a[i] = j;
    dfs(i + 1, x + j);
    a[i] = 0;  // 这一步可以不要，因为后面的搜索当中会覆盖掉，但是有些搜索题当中不会覆盖掉，因此就需要添加这一步操作
  }
}

普通深度优先搜索¶

评论