由一道题引发对DFS的思考

[NOIP 2002 普及组] 选数

感觉过于标题的意思了，其实是由这道题来引出深度优先搜索(DFS)

首先看看题目描述：

题目描述

已知 $\large n$ 个整数 $x_1,x_2,\cdots,x_n$，以及$1$个整数$k$($k<n$)。从$n$ 个整数中任选 $k$个整数相加，可分别得到一系列的和。例如当$n=4$，$k=3$，$4$ 个整数分别为 $3,7,12,19$ 时，可得全部的组合与它们的和为：

$3+7+12=22$

$3+7+19=29$

$7+12+19=38$

$3+12+19=34$

现在，要求你计算出和为素数共有多少种。

例如上例，只有一种的和为素数：$3+7+19=29$。

输入格式

第一行两个空格隔开的整数 $n,k$（$1 \le n \le 20$，$k<n$）。

第二行 $n$ 个整数，分别为 $x_1,x_2,\cdots,x_n$（$1 \le x_i \le 5\times 10^6$）。

输出格式

输出一个整数，表示种类数。

输入输出样例 #1

输入 #1

4 3
3 7 12 19

输出 #1

1

说明/提示

【题目来源】

NOIP 2002 普及组第二题

---

具体分析：

主要：是从给定的 n 个整数中任选 k 个整数进行相加，然后统计这些和中为素数的组合的数量。

输入输出分析

• 输入

  • 第一行包含两个用空格隔开的整数 n 和 k，其中 1≤n≤20 且 k<n。n 表示整数的总数，k 表示需要选取的整数个数。
  • 第二行包含 n 个整数 x1,x2,⋯,x**n，每个整数的范围是 1≤x**i≤5×106。

• 输出

• 输出一个整数，表示和为素数的组合的种类数。

问题求解思路：

要解决这个问题，主要分为以下两个关键按步骤：

• 找出n个整数中选取的k个整数的所有组合并求和
• 判断每个组合的和是否是素数

1. 组合选取

   对于n的范围较小 (1≤n≤20)，我们可以使用深度优先搜索算法来枚举所有可能的组合。在此笔者阐述以下什么是深度优先搜素(DFS)算法

   tips: 佬们如果已经了解相关内容可用右侧的那个什么栏进行跳过

   深度优先搜索是一种通过递归的方式遍历所有可能状态或搜索树/图的算法，非常适合解决组合问题，其核心思想是 尽可能深地探索当前路径，直到无法继续前进时才回溯。深度优先搜索具有以下三个特点：

   • 递归实现：纯天然适合递归（函数调用栈自动处理回溯）
   • 回溯机制：当一条路走到尽头时，返回上一个分叉点
   • 时间复杂度：通常为$O(b**d)$ ，b 是分支因子，d是最大深度

   结合例题：在全排列问题中的应用
   P1706 全排列问题

• 问题分析

  • 目标：生成1到n的所有排列（共n!种）
  • 关键约束：每个字只能使用一次
  • 输出要求：按字典顺序排列

• DFS解决思路：

  (1) 状态标识：

  • 当前已选择的数字序列path
  • 记录数字是否已经使用的数字used(从而避免重复)

  (2) 递归过程：

  • 终止条件：path长度等于n时输出结果
  • 遍历选择：对于每个未使用的数字加入数组path并递归
  • 回溯：走到尽头后返回上一个分叉点然后尝试新选择

以下是我的代码实现，但是写了太垃圾用AI优化了以下

#include <cstdio>
int used[15];      // 标记数字是否使用过
int perm[15];      // 当前排列
int n;

// 打印当前排列
void print_perm() {
    for (int i = 1; i <= n; ++i) {
        printf("%5d", perm[i]); // 保持5字符场宽
    }
    printf("\n");
}

// 深度优先搜索生成排列
void dfs(int depth) { // depth表示当前处理的位置
    if (depth > n) {  // 已生成完整排列
        print_perm();
        return;
    }
    
    for (int num = 1; num <= n; ++num) { // 尝试每个数字
        if (!used[num]) {                // 如果该数字未使用
            used[num] = 1;               // 标记使用
            perm[depth] = num;           // 放入当前位置
            dfs(depth + 1);              // 递归处理下一位置
            used[num] = 0;               // 回溯，取消标记
        }
    }
}

int main() {
    scanf("%d", &n);
    dfs(1); // 从第1个位置开始生成
    return 0;
}

这里我给出一个DFS执行流程图（以n=3为例）

graph TD
    A[开始] --> B[选择1]
    B --> C[选择2]
    C --> D[选择3] --> E[输出1,2,3]
    D --> F[回溯到选择2]
    C --> G[选择3] --> H[输出1,3,2]
    G --> I[回溯到选择1]
    B --> J[选择2]
    J --> K[选择1] --> L[输出2,1,3]
    K --> M[回溯到选择2]
    J --> N[选择3] --> O[输出2,3,1]
    N --> P[回溯到开始]
    A --> Q[选择3]
    Q --> R[选择1] --> S[输出3,1,2]
    R --> T[回溯到选择3]
    Q --> U[选择2] --> V[输出3,2,1]

然后对其复杂度进行分析

• 时间复杂度：$O(b**d)$

  (共有n!种排列方案，每种排列生成都需要花费O(n)的时间)

• 同时我们又引入了空间复杂度的概念：O(n) => 递归栈最大深度为n

---

1. 素数判断

了解了DFS之后，现在我们就来思考如何去处理素数判断逻辑，根据我几乎忘得差不多的小学数学来看，素数是指大于1且只能被1和自生整除的正整数，因此要设计判断一个数是否为素数，我们可以从2开始到 $\sqrt[2]{n}$ 进行遍历，如果该数字能被其中任何一个整除，则这个数不是素数，反之同理

代码实现思路

根据上文我们得知，代码主要有三个部分组成：素数判断函数、深度优先搜索函数和主函数组成

各部分代码实现与解读

1. 素数判断函数

   • 首先，我们需要判断接受的数字n是否小于2，如果小于2就直接false（因为我们是从2遍历到 $\sqrt[2]{n}$ ）且定义上其大小要求大于1
   • 其次从2开始到$\sqrt[2]{n}$进行遍历，如果n能被其中任意一个整数整除，则返回false表示该数不是素数
   • 如果遍历完都没有找到能整除 n 的数，则返回 true，表示是素数。

   实现代码

   bool isPrime(int n) {
    if (n < 2) return false;
    for (int i = 2; i <= sqrt(n); i++) {
        if (n % i == 0) return false;
    }
    return true;
   }

2. 深度优先搜索函数dfs

   • start 表示当前搜索的起始位置，cnt 表示已经选取的数的个数，sum 表示当前选取的数的和。
   • 当 cnt 等于 k 时，说明已经选取了 k 个数，此时调用 isPrime 函数判断 sum 是否为素数，如果是则将结果 ans 加 1。
   • 从 start 开始遍历数组，递归调用 dfs 函数，更新 start 为 i + 1，cnt 为 cnt + 1，sum 为 sum + nums[i]，以继续选取下一个数。

实现代码

void dfs(int start, int cnt, int sum) {
    if (cnt == k) {
        if (isPrime(sum)) {
            ans++;
        }
        return;
    }
    for (int i = start; i < n; i++) {
        dfs(i + 1, cnt + 1, sum + nums[i]);
    }
}

1. 主函数main
   • 首先读取输入的k和n，以及n个整数
   • 调用dfs函数开始搜索，将start、cnt和sum都初始化为0
   • 最后输出结果ans
     实现代码

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

综上，以下是汇总后的完整代码

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

const int MAXN = 25;
int nums[MAXN];
int n, k, ans = 0;

// 更高效的素数判断
bool isPrime(int num) {
    if (num < 2) return false;
    if (num == 2) return true;
    if (num % 2 == 0) return false;
    
    int sqrt_num = sqrt(num);
    for (int i = 3; i <= sqrt_num; i += 2) {
        if (num % i == 0) return false;
    }
    return true;
}

// DFS搜索组合
void dfs(int start, int cnt, int sum) {
    if (cnt == k) {
        if (isPrime(sum)) {
            ans++;
        }
        return;
    }
    
    // 剪枝：剩余元素不足以凑够k个数时提前返回
    if (n - start < k - cnt) return;
    
    for (int i = start; i < n; i++) {
        dfs(i + 1, cnt + 1, sum + nums[i]);
    }
}

int main() {
    scanf("%d%d",&n,&k);
    for (int i = 0; i < n; i++) {
        scanf("%d",&nums[i]);
    }
    dfs(0, 0, 0);
    printf("%d\n",ans);
    return 0;
}

All in One：
因此我们得出，在需要使用DFS进行解题时，针对数据范围必须要进行复杂度分析来防止产生程序超时TLE - Time Limit Exceeded、内存溢出MLE - Meomory Limit Exceeded还有导致错误选择算法(使用了过于简单或复杂的算法)从而导致出现代码在小数据测试通过，但无法判断能否处理最大规模数据或者误用高复杂度算法解决本可用更优方法的问题！

---

复杂度分析

实在是因水平有限，在此摘抄LLM所给出的的时间和空间复杂度分析，仅供参考，若有误欢迎指正！

DFS解法的时间复杂度分析

1. 组合生成复杂度

• 核心操作：DFS需要枚举所有C(n,k)种组合
• 组合数计算：C(n,k) = n!/(k!(n-k)!)
• 最坏情况：当k=n/2时，组合数最大（如n=20,k=10时，C(20,10)=184756）

2. 素数判断复杂度

• 单个和判断：O(√m)，其中m是k个数的和
• 最坏情况：假设每个x_i=5×10⁶，k=10时，m=5×10⁷，√m≈7071

3. 总时间复杂度

• 上界：O(C(n,k) × √m)
• 代入n=20,k=10的最大值：184756 × 7071 ≈ 1.3×10⁹次操作
• 实际表现：由于n≤20，k<n，且现代CPU每秒可处理约10⁸次操作，代码仍可在1秒内完成

4. 空间复杂度

• 递归栈深度：O(k)（每次递归k层）
• 辅助空间：O(n)（存储输入数组）
• 总计：O(n)（k≤n）

---

优化验证（针对题目约束）

1. n≤20的可行性：

   • C(20,10)=184756是最大的组合数
   • 每个和的素数判断约7000次操作
   • 总操作量在可接受范围内

2. 剪枝效果：

   if (n - start < k - cnt) return; // 提前终止无效分支

   • 可减少约50%的递归调用（实测）

3. 素数判断优化：

   • 使用6k±1法可减少约2/3的判断次数

---

复杂度对比表

方法	时间复杂度	适用数据范围
DFS+基础素数判断	O(C(n,k)×√m)	n≤20, k≤10
DFS+6k±1优化	O(C(n,k)×√m/3)	n≤25, k≤12
预处理素数表	O(C(n,k)+m)	m≤10⁷（空间换时间）

---

实际测试数据示例

输入：

20 10
[20个5×10⁶的数]

计算过程：

1. 生成C(20,10)=184756种组合
2. 每个和=5×10⁷，判断素数≈7071次操作
3. 总操作量≈1.3×10⁹（现代CPU约1-2秒完成）

---

结论

• 时间复杂度：O(C(n,k)×√m)（组合数×素数判断）
• 空间复杂度：O(n)（递归栈深度）
• 可行性：完全满足题目约束（n≤20时，C(n,k)最大约2×10⁵）

能引得大佬阅此文，小生三生有幸！