如何编写最小无法凑出零钱算法的暴力破解解法？

针对给定硬币数组求无法凑出的最小零钱金额的问题，暴力解法实现思路和代码如下：

核心思路 #

不需要对硬币做排序预处理，从最小的正整数1开始依次向上校验每个金额：

• 若当前金额可以用给定的硬币组合凑出（每个硬币仅可使用一次），则继续校验下一个更大的金额
• 第一个无法被凑出的金额就是最终的返回结果

实现代码 #

以下是JavaScript版本的实现，和你提供的贪心解法测试结果一致：

function nonConstructibleChangeBruteForce(coins) {
    let checkAmount = 1;
    // 循环校验每个金额
    while (true) {
        if (!canForm(checkAmount, coins)) return checkAmount;
        checkAmount++;
    }
}

// 辅助函数：递归判断目标金额是否可被凑出
function canForm(target, coins, index = 0) {
    if (target === 0) return true;
    if (target < 0 || index >= coins.length) return false;
    // 两种分支：使用当前位置硬币 / 不使用当前位置硬币
    return canForm(target - coins[index], coins, index + 1) || canForm(target, coins, index + 1);
}

// 测试用例，输出结果为20，和贪心解法结果一致
console.log(nonConstructibleChangeBruteForce([5, 7, 1, 1, 2, 3, 22]));

复杂度说明 #

暴力解法的时间复杂度很高，假设最小无法凑出的金额为k，硬币总数为n，递归回溯校验的时间复杂度为O(k*2^n)，仅适合小数据量的验证场景，生产环境更推荐使用你原有的排序+贪心的O(nlogn)解法。

内容的提问来源于stack exchange，提问作者user17399782