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

问题描述：有限硬币组合求和

“有限硬币组合求和”问题要求我们判断，给定一组面额各异的硬币（每种硬币只能使用一次），能否凑成一个特定的目标总和。例如，给定硬币 {1, 5, 16} 和目标金额 6，我们可以用 1 + 5 凑成，因此结果为真。如果目标金额是 8，则无法凑成，结果应为假。这是一个典型的子集和问题变种，通常可以通过递归或动态规划解决。

原始递归尝试与常见陷阱

在尝试解决此类问题时，初学者常会采用一种直观的递归思路：遍历所有硬币，对于当前硬币，如果目标金额大于或等于它，就尝试将其包含在内，然后递归处理剩余硬币和减去当前硬币后的目标金额。

然而，在这种实现中，存在两个常见的陷阱：

1. 数组复制错误： 在递归调用中，为了模拟“使用一次”的限制，需要将当前硬币从硬币列表中移除。如果手动复制数组，很容易出现索引错误。例如，原始代码中的 red[it] = coins[i] 是一个典型的错误。在构建新数组 red 时，意图是复制除 coins[i] 之外的所有元素，但正确的做法应该是复制 coins[x]，其中 x 是遍历原始 coins 数组的索引。即 red[it] = coins[x] 才是正确的复制方式。
2. 效率问题： 每次递归调用都通过循环遍历硬币数组，并在循环内部创建一个新的、长度减一的数组。这种做法不仅增加了代码的复杂性，也带来了显著的性能开销。每次递归层级都会进行不必要的数组创建和元素复制，导致时间复杂度远超预期。

考虑以下原始代码片段中的错误示例：

// 错误示例：数组复制逻辑有误
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]);
    }
}

这个错误会导致新数组 red 中填充的都是被跳过的 coins[i] 的值，而不是原始数组中其他硬币的值，从而产生不正确的结果。

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

解决此类问题的更优雅且高效的递归方法是采用“包含或排除”策略。对于当前考虑的硬币（通常是数组的第一个元素），我们有两种选择：

1. 不包含当前硬币： 我们跳过当前硬币，直接递归处理剩余的硬币和不变的目标金额。
2. 包含当前硬币： 我们使用当前硬币，然后递归处理剩余的硬币和减去当前硬币面额后的目标金额。

只要这两种情况中的任何一种能够成功凑成目标金额，那么总和就是可达的。这种方法避免了复杂的循环和手动数组复制，而是通过递归参数的巧妙设计来处理子问题。

琅琅配音

全能AI配音神器

下载

核心思想：

• 基本情况 (Base Cases):
  • 如果目标金额 goal 为 0，说明已经成功凑成，返回 true。
  • 如果硬币列表 coins 为空或者目标金额 goal 小于 0（说明超出了目标），则无法凑成，返回 false。
• 递归步骤 (Recursive Step):
  • 取出当前硬币 coins[0]。
  • 创建新的硬币列表 tailOfCoins，包含 coins 中除 coins[0] 之外的所有硬币。
  • 递归调用 go(tailOfCoins, goal)：表示不使用 coins[0]，尝试用剩余硬币凑成 goal。
  • 递归调用 go(tailOfCoins, goal - coins[0])：表示使用 coins[0]，尝试用剩余硬币凑成 goal - coins[0]。
  • 如果上述任一调用返回 true，则最终结果为 true。

这种方法的优势在于：

• 清晰简洁： 逻辑更易于理解和实现。
• 避免手动复制错误： 利用 Arrays.copyOfRange 等工具函数可以安全高效地创建子数组。
• 效率提升： 虽然时间复杂度仍为指数级 (O(2^N)，其中 N 是硬币数量)，但它避免了在每次循环迭代中重复创建数组，从而减少了常数因子，提高了实际运行效率。

核心代码实现

以下是采用“包含或排除”策略的优化递归实现：

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
    }
}

注意事项与总结

• 递归基的准确性： 正确定义递归的终止条件至关重要。goal == 0 是成功条件，而 coins.length == 0 || goal
• 数组的不可变性与子数组创建： 在递归中传递数组时，通常需要确保每次递归调用都处理一个“新”的子问题状态。使用 Arrays.copyOfRange 可以方便地创建子数组，避免原始数组被修改，这对于递归的正确性至关重要。
• 时间复杂度： 尽管优化后的代码更简洁，但其时间复杂度仍为指数级 (O(2^N))，对于大规模的硬币数量 N，性能可能成为瓶颈。在这种情况下，可以考虑使用动态规划（背包问题变种）来优化到伪多项式时间复杂度。
• 问题建模： 许多组合问题都可以抽象为“包含或排除”某个元素，然后递归解决子问题。熟练掌握这种思维模式有助于解决多种类似问题。

通过采用这种优化的递归策略，我们不仅修复了原始代码中的数组复制错误，还显著提升了代码的清晰度和可维护性，为解决有限硬币组合求和问题提供了一个高效且易于理解的递归解决方案。