有限硬币求和：递归算法的优化与实现

boolean go(int[] coins, int goal) {
  boolean ans = false;
  // 基本情况：如果目标金额为0，则成功
  if (goal == 0) {
    return true;
  } else if (goal < 0) { // 如果目标金额小于0，则失败
    return false;
  }

  // 遍历所有硬币
  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)) { // 复制除了第i个硬币之外的所有硬币
          // 潜在错误点：这里应复制coins[x]，而非coins[i]
          red[it] = coins[i]; // 错误：这里应该写 coins[x]
          it += 1;
        }
      }
      // 递归调用，尝试用剩余硬币凑成剩余金额
      ans = go(red, goal - coins[i]);
    }
  }
  return ans;
}

// ...
      for (int x = 0; x < coins.length; x++) {
        if (!(i == x)) { // 如果当前硬币不是我们要排除的那个
          red[it] = coins[x]; // 正确：复制数组中索引为x的硬币
          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，说明已经凑成，返回 true。
        if (goal == 0) {
            return true;
        }
        // 基本情况2：
        // 如果没有硬币了（coins.length == 0）或者目标金额小于0，
        // 且目标金额不为0，则说明无法凑成，返回 false。
        if (coins.length == 0 || goal < 0) {
            return false;
        }

        // 递归步骤：
        // 获取除了第一个硬币之外的剩余硬币数组。
        int[] tailOfCoins = Arrays.copyOfRange(coins, 1, coins.length);

        // 选项1：不使用当前第一个硬币 (coins[0])。
        // 递归地在剩余硬币中寻找是否能凑成原目标金额。
        boolean excludeCurrentCoin = canMakeSum(tailOfCoins, goal);

        // 选项2：使用当前第一个硬币 (coins[0])。
        // 递归地在剩余硬币中寻找是否能凑成 (goal - coins[0])。
        boolean includeCurrentCoin = canMakeSum(tailOfCoins, goal - coins[0]);

        // 如果两种情况中任意一种能凑成，则返回 true。
        return excludeCurrentCoin || includeCurrentCoin;
    }

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

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

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

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

        int[] coins5 = {1, 2, 3};
        int goal5 = 0; // 预期: true (目标金额为0，无需任何硬币)
        System.out.println("Coins: " + Arrays.toString(coins5) + ", Goal: " + goal5 + " -> " + canMakeSum(coins5, goal5));
    }
}