题解 | #最小邮票数#

#include <iostream>
using namespace std;
int N, M, cnt = 0, mincount = 1e9, flag;
void dg(int cnt, int value, int v[], int k) {
    if (value == M) {
        if (cnt < mincount)mincount = cnt;
        flag = 1;
        return;
    }
    for (int i =k; i < N; i++) {
        if (value + v[i] <= M) {
            dg(cnt + 1, value + v[i], v, i+1);
        }
    }
}
int main() {
    cin >> M >> N;
    int v[N + 10]; //第i张邮票的面额
    for (int i = 0; i < N; i++) {
        cin >> v[i];
    }
    dg(0, 0, v, 0);  //递归搜索，若不符合条件的数值，则不选，否则选入
    if (flag == 1) {
        cout << mincount << endl;
    } else {
        cout << 0 << endl;
    }
}
// 64 位输出请用 printf("%lld")