Day 18 · DFS 入门：枚举所有方案

题意：从 1, 2, …, n 里任取 r 个数，输出所有组合。每个组合占一行、元素按从小到大排列、每个数字占 3 个字符宽度，所有组合按字典序输出。

思路

就是第 4 节讲的「下标递增」框架，一个字都不用改：

• 状态：step（当前填第几位，从 0 开始）+ start（这一位最小能填几）
• 选择：这一位填 start ~ n 里的任意一个
• 边界：step == r → 输出这一行，return

5 3

  1  2  3
  1  2  4
  1  2  5
  1  3  4
  1  3  5
  1  4  5
  2  3  4
  2  3  5
  2  4  5
  3  4  5

说明：题面样例在网上流传的纯文本版本里，第一行的前导空格常被吃掉。 但题目明确要求「每个元素占三个字符的位置」，所以每一行开头都有两个空格（个位数占不满 3 格，前面补空格）。

完整代码

#include <iostream>
#include <iomanip>
using namespace std;

int n, r;
int a[25];      // 存放当前正在拼的组合

// step：现在要填第几个数（从 0 开始）
// start：这一位最小能填几（★ 保证组合内部严格递增，从而不重复）
void dfs(int step, int start){
    if(step == r){                       // 边界：已经选满 r 个数
        for(int i = 0; i < r; i++) cout << setw(3) << a[i];
        cout << "\n";
        return;
    }
    for(int i = start; i <= n; i++){     // 只能从 start 往后选
        a[step] = i;
        dfs(step + 1, i + 1);            // ★ 下一层从 i+1 开始，不许回头
    }
}

int main(){
    cin >> n >> r;
    dfs(0, 1);
    return 0;
}

易错点

• 忘了 #include <iomanip>：setw 编译不过。
• 把 dfs(step+1, i+1) 误写成 dfs(step+1, i)：会出现 1 1 1、1 2 2 这种非法组合， 而且方案数暴涨。
• start 传错成 1：等价于全排列，每种组合重复 3! 倍。
• 边界写成 step == n：应该是 step == r（选够 r 个就停，不是填满 n 个位置）。
• 用 endl：18 万行输出时会慢一截，用 "\n"。
• 数组开小了：r 最大 20，a[25] 够用，但别只开 a[20]。

题意：按字典序输出 1 ~ n 的所有不重复排列，每行一个序列，每个数字占 5 个字符宽度。

思路

用第 5 节的排列框架。关键是那个 vis 数组：它记录的不是「用了几个」，而是「具体哪一个被用了」。

为什么不能用 start 递增来防重复？因为排列里顺序是有意义的：1 2 3 和 2 1 3 都是合法答案。 所以「不许回头」这条规则在这里是错的，只能靠标记「这个数用过了没有」。

3

    1    2    3
    1    3    2
    2    1    3
    2    3    1
    3    1    2
    3    2    1

同上：每行开头有 4 个空格（个位数占 5 格宽度的补位）。

完整代码

#include <iostream>
#include <iomanip>
using namespace std;

int n;
int a[15];          // 当前排列
bool vis[15];       // vis[i] = true 表示数字 i 已经用过了

void dfs(int step){
    if(step > n){                       // 边界：n 个位置都填好了
        for(int i = 1; i <= n; i++) cout << setw(5) << a[i];
        cout << "\n";
        return;
    }
    for(int i = 1; i <= n; i++){        // 从小到大试每一个还没用过的数
        if(!vis[i]){
            vis[i] = true;              // 进入时标记
            a[step] = i;
            dfs(step + 1);
            vis[i] = false;             // ★ 退出时撤销（回溯）
        }
    }
}

int main(){
    cin >> n;
    dfs(1);
    return 0;
}

易错点

• 忘了写 vis[i] = false;：这是全排列题的头号杀手。忘了撤销，n=3 时只会输出 1 行 1 2 3，其余全丢。
• 用了 start 递增那套：那是组合的套路。排列里 2 1 3 是合法答案，用 start 会把一半方案砍掉。
• 边界写成 step == n：那最后一个位置就没填。要用 step > n，搭配从 dfs(1) 开始。
• 输出宽度写错：题目要 5 个场宽，写成 3 或 4 都会 PE（格式错误）。
• 数组开小了：a[15] 和 vis[15] 对应 n ≤ 9，注意 vis 下标到 n 为止，n=9 时刚好够；如果题目 n 到 10 就要开到 11 以上。
• 忘了 #include <iomanip>。

题意：给出 n 个整数和整数 k（k < n）。从 n 个数里任选 k 个相加， 能得到一堆和。问：这些和里面，素数有多少个？

例如 n=4, k=3, 数是 3 7 12 19，四种选法的和分别是 22、29、38、34， 只有 29 是素数，所以答案是 1。

思路

这是最标准的「选或不选」框架，加一个剪枝：

• 站在第 idx 个数面前，chosen 表示已经选了几个，sum 是当前的和
• 选：dfs(idx+1, chosen+1, sum + x[idx])
• 不选：dfs(idx+1, chosen, sum)
• 边界 1：chosen == k → 判断 sum 是不是素数，是就 ans++，return
• 边界 2：idx > n → 数用完了还没选够，return
• 剪枝：n - idx + 1 < k - chosen → 剩下的数不够选，return

4 3
3 7 12 19

1

完整代码

#include <iostream>
using namespace std;

int n, k;
int x[25];
int ans = 0;

bool isPrime(long long v){
    if(v < 2) return false;                  // 0 和 1 都不是素数
    for(long long d = 2; d * d <= v; d++){   // 试除到 √v 就够
        if(v % d == 0) return false;         // ★ 找到因子立刻退出
    }
    return true;
}

// idx：正在考虑第 idx 个数（1 开始）
// chosen：已经选了几个
// sum：已选数字之和
void dfs(int idx, int chosen, long long sum){
    if(chosen == k){                    // 选够了，判断和是不是素数
        if(isPrime(sum)) ans++;
        return;
    }
    if(idx > n) return;                 // 数用完了还没选够
    if(n - idx + 1 < k - chosen) return; // ★ 剪枝：剩下的数不够选了

    dfs(idx + 1, chosen + 1, sum + x[idx]);   // 选第 idx 个
    dfs(idx + 1, chosen, sum);                // 不选第 idx 个
}

int main(){
    cin >> n >> k;
    for(int i = 1; i <= n; i++) cin >> x[i];
    dfs(1, 0, 0);
    cout << ans << endl;
    return 0;
}

易错点

• isPrime 忘了处理 v < 2：0 和 1 都不是素数，漏判会把它们算成素数。虽然本题 x_i ≥ 1、k ≥ 1， 和最小是 1，还是补上更保险。
• 循环条件写成 d <= v/2 或 d <= v：能过但慢得离谱。要用 d * d <= v（试除到 √v）。
• 索引从 1 开始但数组只开了 n：int x[25] 是安全的，但别写成 int x[20]。
• 「选/不选」两个分支的顺序：本题不影响答案（只是数的顺序不同），但如果题目要求按字典序输出方案，就必须先「选」后「不选」。
• 剪枝写反了：是「剩下的少于需要的」（n-idx+1 < k-chosen）才返回，写成 > 会把正常分支也砍掉。

题意：把一个自然数 n（n > 1）拆成若干个小于 n 的自然数之和。 每个拆分里的数字要从小到大排列，输出所有拆分，按字典序。

比如 n=7，答案以 1+1+1+1+1+1+1 开头，以 3+4 结尾，共 14 行。 注意 7 自己不算（题目要求加数都小于 n，所以至少要拆成两个数）。

思路

还是第 4 节的「有序枚举」框架，只是把「选下标」换成「填加数」：

• 状态：pos（正在填第几个加数）、remain（还差多少凑够 n）、start（这一位最小能填几）
• 选择：这一位填 start ~ remain 里的任意一个数
• 边界：remain == 0 → 凑齐了，输出
• 去重 + 有序：下一位传 i（不是 i+1），保证「后面的数不小于前面的数」

7

1+1+1+1+1+1+1
1+1+1+1+1+2
1+1+1+1+3
1+1+1+2+2
1+1+1+4
1+1+2+3
1+1+5
1+2+2+2
1+2+4
1+3+3
1+6
2+2+3
2+5
3+4

完整代码

#include <iostream>
using namespace std;

int n;
int a[15];      // 存当前这一组加数

// pos：现在要决定第 pos 个加数
// remain：还差多少才能凑够 n
// start：这一位最小能填几（★ 强制不减，避免出现重复方案）
void dfs(int pos, int remain, int start){
    if(remain == 0){                 // 正好凑齐
        if(pos < 2) return;          // ★ 至少要有两个加数（不能只有 n 自己）
        for(int i = 0; i < pos; i++){
            if(i) cout << "+";        // 第一个数前面不加加号
            cout << a[i];
        }
        cout << "\n";
        return;
    }
    for(int i = start; i <= remain; i++){   // 试这一位填 i
        a[pos] = i;
        dfs(pos + 1, remain - i, i);        // ★ 下一位至少从 i 开始（可以相等）
    }
}

int main(){
    cin >> n;
    dfs(0, n, 1);
    return 0;
}

易错点

• 传 i+1 而不是 i：重复加数被禁掉，答案少一大半（n=7 只剩 4 行）。
• 没排除「n 自己」：不加 if(pos < 2) return; 的话，第一行会多出 7，答案多 1 行。
• 循环上界写成 i <= n：会产生无效分支（比如还剩 2 却去试 i=5，导致 remain 变负，虽然不会输出但白跑）。写成 i <= remain 更干净。
• 输出的加号位置错：第一个数前面不能有 +。用 if(i) cout << "+"; 是标准写法。
• 数组开小了：n=8 时最长的拆分是 1+1+1+1+1+1+1+1，共 8 个加数，a[15] 足够。
• 用排序去重：有些同学先搜出所有拆分再排序去重，那是「先污染后治理」。 正确做法是从搜索时就保证不产生重复，这样既快又不会漏。