随机数选最少数字求和

本文为最近做过的一道编程笔试题，代码实现方式多种多样，此处本人提供的代码可以获得正确解，仅供大家参考。

一、题目描述

题目描述：
小明用计算机随机生成了N个正整数，他希望从这N个数中选取若干个数，使得它们的和等于M。这些随机生成的数字可能会相同，但是每个数字最多只允许使用一次。
当然这样的选取方案可能不存在，也可能有多个。
现在希望编写一个程序，能够找出数字个数最少的选取方案，输出对应的最少数字的个数，如果无解输出“No solution”。
输入描述：

• 单组输入，每组输入2行。
• 第1行包含两个正整数N和M，分别表示初始输入的正整数个数和目标数字和（N<=1e3，M<=1e5）。
• 第2行为N个正整数，两两之间用空格隔开（每一个正整数均小于等于1e5）。

输出描述：

• 输出数字个数最少的选取方案中所包含的最少数字个数，如果无解输出“No solution”。

样例：

• 输入

  5 5
  1 3 2 1 1
  

• 输出

  2
  

二、实现代码程序

代码实现如下：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

vector<int> findCombination(vector<int>& numbers, int target) {
    vector<int> combination;
    sort(numbers.begin(), numbers.end(), greater<int>());

    for (int num : numbers) {
        if (num <= target) {
            combination.push_back(num);
            target -= num;
        }
    }

    if (target == 0) {
        return combination;
    } else {
        combination.clear();
        return combination;
    }
}

int main() {
    int N, M;
    cin >> N >> M;

    vector<int> numbers(N);
    for (int i = 0; i < N; ++i) {
        cin >> numbers[i];
    }

    vector<int> solution = findCombination(numbers, M);

    if (!solution.empty()) {
        cout << solution.size() << endl;
    } else {
        cout << "No solution" << endl;
    }

    return 0;
}

三、测试结果截图

输入：

5 5
1 3 2 1 1

输出结果如下：