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

问题描述：有限硬币求和

“有限硬币求和”问题是一个经典的组合问题。其核心在于：给定一个整数数组 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 对应的硬币之外的所有其他硬币。这个错误导致递归调用时传递的硬币集合是错误的，从而影响了最终结果。

紫东太初

中科院和武汉AI研究院推出的新一代大模型

下载

此外，在每次递归调用中都通过循环手动创建并复制一个新数组，会带来显著的时间开销，尤其是在硬币数量较多时，其时间复杂度会非常高。

优化递归策略：包含或排除

为了解决上述问题并提高效率，我们可以采用一种更简洁、更符合递归思想的策略：对于当前考虑的硬币，我们有两种选择——包含它或排除它。

这种策略的核心思想是：

1. 选择第一个硬币 coins[0]。
2. 情况一：不使用 coins[0]。 此时，问题转化为从剩余的硬币 coins[1...n-1] 中凑出原目标金额 goal。
3. 情况二：使用 coins[0]。 此时，问题转化为从剩余的硬币 coins[1...n-1] 中凑出 goal - coins[0]。
4. 如果以上两种情况中任意一种能够成功，则说明目标金额可以凑成。

代码实现与解析

基于“包含或排除”的策略，我们可以得到一个更优雅、更高效的递归实现：

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 (超出了，无法凑成正