问题描述：有限硬币求和
“有限硬币求和”问题是一个经典的组合问题。其核心在于：给定一个整数数组 coins，代表不同面额的硬币，每种面额的硬币仅有一枚；以及一个目标金额 goal。我们需要编写一个函数，判断是否能够从这组硬币中选择若干枚（每枚最多使用一次）使得它们的总和恰好等于 goal。例如，硬币面额为 [1, 5, 16]，目标金额为 6，则可以通过 1 + 5 = 6 凑成，应返回 true。
初始递归尝试与常见陷阱
在解决这类问题时，递归是一种直观的思路。一种常见的递归策略是遍历所有可用硬币，尝试使用其中一枚，然后对剩余硬币和剩余目标金额进行递归调用。然而，这种方法在实现过程中容易引入错误，尤其是在处理硬币集合的传递时。
考虑以下一种常见的初始递归实现思路：
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;
}关键错误分析
上述代码中存在一个关键的逻辑错误，导致部分测试用例（如 [111, 1, 2, 3, 9, 11, 20, 30] 目标 8）返回错误结果。问题出在硬币数组 red 的复制逻辑上：
for (int x = 0; x < coins.length; x++) {
if (!(i == x)) {
red[it] = coins[i]; // 错误点
it += 1;
}
}这里的 red[it] = coins[i] 语句意味着在构建新数组 red 时，它会反复将当前循环中被“移除”的硬币 coins[i] 复制进去，而不是将 coins 数组中除了 coins[i] 之外的其他硬币复制进去。正确的做法应该是 red[it] = coins[x]，以确保 red 数组包含了 coins 数组中除了索引 i 对应的硬币之外的所有其他硬币。这个错误导致递归调用时传递的硬币集合是错误的，从而影响了最终结果。
此外，在每次递归调用中都通过循环手动创建并复制一个新数组，会带来显著的时间开销，尤其是在硬币数量较多时，其时间复杂度会非常高。
优化递归策略：包含或排除
为了解决上述问题并提高效率，我们可以采用一种更简洁、更符合递归思想的策略：对于当前考虑的硬币，我们有两种选择——包含它或排除它。
这种策略的核心思想是：
- 选择第一个硬币 coins[0]。
- 情况一：不使用 coins[0]。 此时，问题转化为从剩余的硬币 coins[1...n-1] 中凑出原目标金额 goal。
- 情况二：使用 coins[0]。 此时，问题转化为从剩余的硬币 coins[1...n-1] 中凑出 goal - coins[0]。
- 如果以上两种情况中任意一种能够成功，则说明目标金额可以凑成。
代码实现与解析
基于“包含或排除”的策略，我们可以得到一个更优雅、更高效的递归实现：
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 (超出了，无法凑成正 
