递归解决有限硬币组合求和问题：优化与常见陷阱

// 错误示例：数组复制逻辑有误
for (int i = 0; i < coins.length && (!ans); i++) {
    if (goal >= 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]; // 此处应为 red[it] = coins[x];
                it += 1;
            }
        }
        ans = go(red, goal - coins[i]);
    }
}

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:
        // 如果硬币列表为空（没有硬币可用），或者目标金额小于0（超出了目标），
        // 则无法凑成。
        if (coins.length == 0 || goal < 0) {
            return false;
        }

        // 递归步骤:
        // 1. 获取当前硬币（数组的第一个元素）
        int currentCoin = coins[0];
        // 2. 创建一个新数组，包含除当前硬币之外的所有硬币
        int[] remainingCoins = Arrays.copyOfRange(coins, 1, coins.length);

        // 3. 两种可能性：
        //    a) 不使用当前硬币：递归调用 canMakeSum(remainingCoins, goal)
        //    b) 使用当前硬币：递归调用 canMakeSum(remainingCoins, goal - currentCoin)
        // 只要其中一种情况能凑成目标，就返回 true。
        return canMakeSum(remainingCoins, goal) || canMakeSum(remainingCoins, goal - currentCoin);
    }

    public static void main(String[] args) {
        // 测试案例
        int[] coins1 = {1, 5, 16};
        int goal1 = 6; // 1 + 5 = 6
        System.out.println("Coins: " + Arrays.toString(coins1) + ", Goal: " + goal1 + " -> " + canMakeSum(coins1, goal1)); // 预期: true

        int[] coins2 = {111, 1, 2, 3, 9, 11, 20, 30};
        int goal2 = 8; // 无法凑成 8
        System.out.println("Coins: " + Arrays.toString(coins2) + ", Goal: " + goal2 + " -> " + canMakeSum(coins2, goal2)); // 预期: false

        int[] coins3 = {2, 3, 5};
        int goal3 = 7; // 2 + 5 = 7
        System.out.println("Coins: " + Arrays.toString(coins3) + ", Goal: " + goal3 + " -> " + canMakeSum(coins3, goal3)); // 预期: true

        int[] coins4 = {10, 20, 30};
        int goal4 = 5; // 无法凑成
        System.out.println("Coins: " + Arrays.toString(coins4) + ", Goal: " + goal4 + " -> " + canMakeSum(coins4, goal4)); // 预期: false

        int[] coins5 = {1, 2, 3};
        int goal5 = 0; // 目标为0，直接返回true
        System.out.println("Coins: " + Arrays.toString(coins5) + ", Goal: " + goal5 + " -> " + canMakeSum(coins5, goal5)); // 预期: true
    }
}