递归解决有限硬币求和问题：原理、陷阱与优化实践

boolean go(int[] coins, int goal) {
    boolean ans = false;
    if (goal == 0) { // 目标金额为0，说明已凑成
        return true;
    } else if (goal < 0) { // 目标金额小于0，说明凑不成
        return false;
    }

    for (int i = 0; i < coins.length && (!ans); i++) {
        if (goal >= coins[i]) {
            // 尝试使用当前硬币 coins[i]
            // 创建一个新数组 red，包含除 coins[i] 之外的所有硬币
            int[] red = new int[coins.length - 1];
            int it = 0;
            for (int x = 0; x < coins.length; x++) {
                if (!(i == x)) {
                    // ❌ 错误：这里应该复制 coins[x] 而不是 coins[i]
                    red[it] = coins[i]; // 总是复制当前循环的硬币 coins[i]
                    it += 1;
                }
            }
            // 递归调用，目标金额减少，硬币集合也减少
            ans = go(red, goal - coins[i]);
        }
    }
    return ans;
}

for (int x = 0; x < coins.length; x++) {
    if (!(i == x)) {
        red[it] = coins[i]; // 错误点
        it += 1;
    }
}

import java.util.Arrays; // 需要导入 Arrays 类

public class FiniteCoinsSum {

    /**
     * 判断是否能从给定硬币集合中凑成目标金额，每种硬币最多使用一次。
     *
     * @param coins 硬币面额数组，每种硬币仅有一枚。
     * @param goal 目标金额。
     * @return 如果能凑成，返回 true；否则返回 false。
     */
    public static boolean canMakeSum(int[] coins, int goal) {
        // 基本情况 1: 目标金额为 0，说明已经成功凑成
        if (goal == 0) {
            return true;
        }
        // 基本情况 2:
        // a) 没有硬币了，但目标金额不为 0
        // b) 目标金额小于 0 (超出了，无法凑成正