1. 题目背景与需求分析
这道编程题来自GESP(青少年编程能力等级考试)2025年9月认证的C++五级真题。作为认证考试中较高级别的题目,它主要考察考生对算法设计、数据结构应用和编程实现能力的掌握程度。
题目要求实现一个"数字选取"功能:给定一个包含n个正整数的数组,需要从中选取若干个数字,使得这些数字的和恰好等于给定的目标值k。需要注意的是,每个数字只能被选取一次,且需要找出所有可能的选取方案。
这类问题在实际开发中非常常见,比如:
- 电商平台的优惠券组合计算
- 游戏中的装备合成系统
- 金融领域的投资组合优化
需要模型API调用? 免费领10W Token,多模型网关一键接入 Claude、DeepSeek 等主流模型。
2. 算法思路解析
2.1 问题归类与算法选择
这本质上是一个典型的"子集和问题"(Subset Sum Problem),属于NP完全问题。对于这类问题,当数据规模较小时,回溯算法是最直观有效的解决方案。
为什么选择回溯算法而不是动态规划?
- 题目要求输出所有可能的解,而不仅仅是判断是否存在解
- GESP五级考试更注重考察基础算法实现能力
- 回溯算法的思路更直观,适合教学和考试场景
2.2 回溯算法框架设计
回溯算法的核心框架如下:
- 定义一个结果集存储所有有效解
- 递归遍历所有可能的数字选择
- 在每一步做出选择后继续递归
- 当满足条件时将当前解加入结果集
- 撤销上一步选择(回溯)尝试其他可能性
具体到本题:
- 选择条件:当前数字未被使用过
- 终止条件:当前和等于目标值k
- 剪枝条件:当前和超过k时可以提前终止
3. 代码实现详解
3.1 基础数据结构定义
首先我们需要定义几个关键变量:
cpp复制vector<vector<int>> result; // 存储所有有效解
vector<int> path; // 当前路径/解
vector<bool> used; // 标记数字是否被使用过
3.2 核心回溯函数实现
cpp复制void backtrack(vector<int>& nums, int target, int startIndex, int sum) {
if (sum == target) {
result.push_back(path
