设计算法求解和恰好为 k 的元素个数最小的解。给定若干个正整数 a0、 a1 、…、an-1 ，从中选出若干数，使它们的和恰好为 k，要求找选择元素个数最 少的解。（问题设定：n=5; k=10）利用回溯法求解，并输出问题解。c+

以下是使用回溯法求解的 C++ 代码：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int n = 5, k = 10; // 全局变量，n为数组大小，k为目标和
vector<int> arr(n); // 存储输入的数组
vector<int> tmp, ans; // 存储当前选择的元素，和最终的解

// 求解和为sum的子集，返回子集中元素个数最小值
int dfs(int idx, int sum) {
    if (sum == k) { // 找到满足条件的子集
        if (ans.empty() || tmp.size() < ans.size()) { // 更新最优解
            ans = tmp;
        }
        return ans.size();
    }
    if (sum > k || idx == n) { // 剪枝
        return -1;
    }
    tmp.push_back(arr[idx]); // 选择当前元素
    int cnt1 = dfs(idx + 1, sum + arr[idx]); // 继续向下搜索
    tmp.pop_back(); // 取消选择
    int cnt2 = dfs(idx + 1, sum); // 不选当前元素
    if (cnt1 == -1) return cnt2; // 当前分支不满足条件
    if (cnt2 == -1) return cnt1; // 当前分支不满足条件
    return min(cnt1, cnt2); // 返回当前分支的最优解
}

int main() {
    // 输入数组
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    // 回溯搜索
    int cnt = dfs(0, 0);
    // 输出结果
    cout << "元素个数最少为：" << cnt << endl;
    cout << "选择的元素为：";
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
    cout << endl;
    return 0;
}

该算法的时间复杂度为 $O(2^n)$，由于每个元素有选和不选两种状态，共有 $2^n$ 种可能的选择方案。因此该算法对于大规模问题并不适用，但对于本题规模较小的情况，可以快速得到正确解。