题解 | #最小邮票数#

#include <stdio.h>

int minStamps;

// target:还需要的目标数
void dfs(int target, int currentStamps, int index, int n, int* stamps) {
    if (target == 0) {
        // 达到目标值，更新最小邮票张数
        if (currentStamps < minStamps) {
            minStamps = currentStamps;
        }
        return;
    }

    if (index == n || target < 0) {
        // 遍历完所有邮票或者目标值小于0，回溯
        return;
    }

    // 选择当前邮票
    // 确保每次index+1
    dfs(target - stamps[index], currentStamps + 1, index + 1, n, stamps);

    // 不选择当前邮票，继续下一张邮票
    dfs(target, currentStamps, index + 1, n, stamps);
}

int main() {
    int total;// 目标总数
    while (scanf("%d", &total) != EOF) { 
        int count;// 邮票张数
        scanf("%d", &count);
        int stamps[count];
        for (int i = 0; i < count; i++)
        {
            scanf("%d", &stamps[i]);
        }
        minStamps = 20;
        dfs(total,0,0,count,stamps);
        if(minStamps == 20){
            printf("%d",0);
        }else{
            printf("%d",minStamps);
        }
    }
    return 0;
}