问题描述与初始递归尝试
有限硬币求和问题要求我们判断给定的一组硬币（每种面额仅一枚）是否能组合成一个特定的目标金额。例如，给定硬币 [1, 5, 16] 和目标金额 6，我们可以用 1 + 5 凑成，因此结果为 true。
在尝试使用递归解决此类问题时，一种常见的思路是遍历所有硬币，对于每枚硬币，尝试将其用于构成目标金额，然后递归地处理剩余的硬币和减少后的目标金额。
考虑以下一种初步的递归实现思路：
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;
}识别并修正代码中的关键错误
上述代码在处理硬币数组 red 的复制时存在一个关键错误。在内部循环中，当尝试构建一个不包含当前硬币 coins[i] 的新数组 red 时，代码 red[it] = coins[i] 实际上是将 当前正在被排除的硬币 coins[i] 复制到了新数组 red 中，而不是将 未被排除的其他硬币 coins[x] 复制进去。
正确的复制方式应该是：
// ...
for (int x = 0; x < coins.length; x++) {
if (!(i == x)) { // 如果当前硬币不是我们要排除的那个
red[it] = coins[x]; // 正确：复制数组中索引为x的硬币
it += 1;
}
}
// ...这个错误会导致新生成的 red 数组内容不正确，从而影响后续的递归判断，可能导致错误的结果（例如，在不应该凑成的情况下返回 true）。
优化递归策略：包含或排除
除了修复数组复制错误，我们还可以采用一种更简洁、更符合递归思想的策略来解决这个问题，即“包含或排除”策略。对于当前考虑的每一枚硬币，我们都有两种选择：
- 包含这枚硬币：将目标金额减去这枚硬币的面额，然后递归地在 剩余的硬币 中寻找解决方案。
- 排除这枚硬币：不使用这枚硬币，直接递归地在 剩余的硬币 中寻找解决方案，目标金额不变。
如果这两种情况中的任意一种能够凑成目标金额，那么总的来说就是成功的。这种方法避免了在循环中构建新数组的复杂性，而是通过 Arrays.copyOfRange 简单地处理剩余硬币。
正确且优化的递归实现
以下是基于“包含或排除”策略的优化实现：
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));
}
}时间复杂度分析
这种“包含或排除”的递归策略，对于每个硬币，我们都做了两次递归调用（一次包含，一次排除）。如果硬币数组中有 N 枚硬币，那么在最坏情况下，递归树的深度为 N，每个节点有两个分支。因此，其时间复杂度近似为 O(2^N)。
对于 N 值较小的情况，这种指数级的复杂度是可以接受的。然而，当硬币数量 N 较大时（例如 N > 20-25），计算量会急剧增加，可能导致程序运行缓慢甚至栈溢出。
注意事项
- 基本情况（Base Cases）的准确性：递归函数必须有明确的终止条件，以避免无限递归。在这个问题中，goal == 0 (成功) 和 coins.length == 0 || goal
- 数组复制的效率：Arrays.copyOfRange() 方法在每次递归调用时都会创建一个新的硬币数组。虽然它比手动循环复制更简洁，但频繁的数组创建和垃圾回收可能会带来一定的性能开销。对于性能要求极高的场景，可以考虑传递索引范围而不是创建新数组，或者使用动态规划进行优化（如果硬币可以重复使用或存在其他变体）。
- 递归深度与栈溢出：当 coins 数组的长度 N 非常大时，递归深度可能超过 JVM 的默认栈大小，导致 StackOverflowError。在这种情况下，可能需要增加 JVM 的栈大小，或者考虑迭代式的动态规划解决方案。
- 问题变体：本教程解决的是每种硬币只能使用一次的情况。如果硬币可以重复使用（经典的背包问题变体），那么算法逻辑会有所不同，通常会采用动态规划（DP）来解决，以避免重复计算和优化时间复杂度。
总结
解决有限硬币求和问题时，递归是一种直观且强大的工具。关键在于选择正确的递归策略和准确处理基本情况。通过采用“包含或排除”的策略，并利用 Arrays.copyOfRange 简化数组操作，我们可以构建一个清晰且功能正确的递归解决方案。同时，了解其指数级时间复杂度及其潜在的性能瓶颈，对于在实际应用中选择合适的算法至关重要。
