$$dfs$$

深度优先搜索，全称 Depth First Search，通常有两种意义：递归暴力枚举每种情况、图论中用于遍历或搜索图的算法。

搜索：递归暴力枚举每种情况

没有什么好说的，经常用于打暴力~~，像 xhr 神仙就可以用它打出 HN 2023 小学组 S 1=~~。

洛谷 P2089 烤鸡

给定一个整数 $n$，你现在要确定 $10$ 个变量 $x_1,x_2\cdots x_{10}$ 的值，满足 $\sum\limits_{1\leqslant i \leqslant 10} x_i = n$ 且对于每个 $1\leqslant i \leqslant 10$，$1\leqslant x_i \leqslant 3$，输出方案数和每种方案。

要枚举 $10$ 个变量的值，你当然可以写 $10$ 重循环枚举，可如果他要求你枚举 $m$ 个变量的值呢？这时，你就需要用递归来处理。

对于每层递归，枚举每种情况，然后进入下一层递归。当递归枚举完每个数的情况后，判断情况是否满足要求，然后返回上一层递归。

#include <bits/stdc++.h>

using namespace std;

int n, a[15], ans;
vector<vector<int>> v;

void dfs (int x) {
  if (x == 11) {
    vector<int> t;
    int sum = 0;
    for (int i = 1; i <= 10; i++) {
      sum += a[i], t.push_back(a[i]);
    }
    if (sum == n) {
      ans++, v.push_back(t);
    }
    return ;
  }
  a[x] = 1, dfs(x + 1);
  a[x] = 2, dfs(x + 1);
  a[x] = 3, dfs(x + 1);
}

int main () {
  ios::sync_with_stdio(0), cin.tie(0);
  cin >> n;
  dfs(1);
  cout << ans << '\n';
  for (auto i : v) {
    for (int j : i) {
      cout << j << ' ';
    }
    cout << '\n';
  }
  return 0;
}