Coin Change Problem递归回溯算法分支比较方案咨询

核心逻辑说明 #

你当前卡壳的分支结果对比逻辑，不需要等整棵递归树遍历完成后再统一处理：所有合法分支的对比动作，只在递归触达「剩余待凑金额为0」的终止节点时触发——每到这个节点就代表走完了一条完整有效的找零路径，此时拿当前路径的硬币数和全局记录的最优值对比，更优就覆盖保存即可。递归遍历完所有分支后，全局保存的组合就是最优解。

回溯实现必须拆分两类存储结构，不能像原代码一样所有分支共用同一个列表不做清理：

• 临时路径存储：记录当前递归分支正在探索的硬币选择，每次选/不选的操作递归返回后，必须做撤销（回溯），避免不同分支的选择互相污染
• 全局最优存储：每次遇到合法有效组合时，如果比已存的最优组合硬币数更少，就把当前临时路径做深拷贝存为新的最优解（不能直接存临时路径的引用，因为临时路径后续会被回溯修改）

原代码存在的具体问题 #

• 全局共用同一个LinkedList实例，选硬币加入列表后，递归返回没有做删除撤销，不同分支的选择会叠加在同一个列表里，路径数据完全混乱
• 缺少合法组合的终止判断：凑齐目标金额时没有做任何记录、对比动作，根本无法感知有效分支的结果
• 直接返回递归过程中使用的列表引用，列表内容会被后续的回溯操作反复修改，拿到的结果不是某条分支的完整快照
• 没有剪枝逻辑，递归会探索大量不可能得到最优解的分支，效率极低

可运行修正代码 #

import java.util.LinkedList;
import java.util.List;

public class CoinChange_Backtracking {
    static int[] coins = {3, 2, 1};
    static int targetAmount = 3;
    // 临时探索路径
    static List<Integer> currentPath = new LinkedList<>();
    // 全局最优组合快照
    static List<Integer> bestCombination = new LinkedList<>();
    // 已知最少硬币数，初始为无穷大
    static int minCoinCount = Integer.MAX_VALUE;

    public static void main(String[] args) {
        backtrack(0, targetAmount);
        System.out.println("最优找零组合：" + bestCombination);
        System.out.println("最少硬币数量：" + minCoinCount);
    }

    /**
     * 回溯递归函数
     * @param coinIndex 当前处理的硬币面额索引
     * @param remain 剩余待凑金额
     */
    private static void backtrack(int coinIndex, int remain) {
        // 触达合法终止点：当前路径凑齐了目标金额，做对比更新
        if (remain == 0) {
            if (currentPath.size() < minCoinCount) {
                minCoinCount = currentPath.size();
                // 深拷贝当前路径存为最优，避免后续回溯修改内容
                bestCombination = new LinkedList<>(currentPath);
            }
            return;
        }
        // 触达无效终止点：索引越界/剩余金额为负，当前分支走不通
        if (coinIndex >= coins.length || remain < 0) {
            return;
        }
        // 剪枝：当前路径长度已经超过已知最优，不可能得到更优解，直接返回
        if (currentPath.size() >= minCoinCount) {
            return;
        }

        // 分支1：不选当前硬币，直接处理下一个面额
        backtrack(coinIndex + 1, remain);

        // 分支2：选当前硬币（面额不能超过剩余待凑金额）
        if (coins[coinIndex] <= remain) {
            currentPath.add(coins[coinIndex]);
            // 选完后仍可重复选当前面额，索引不变，扣减对应金额
            backtrack(coinIndex, remain - coins[coinIndex]);
            // 回溯核心：递归返回后撤销选择，删除刚加入的硬币
            currentPath.remove(currentPath.size() - 1);
        }
    }
}

运行上述代码，针对示例参数coins={3,2,1}、targetAmount=3，会输出最优组合[3]，符合预期。

可选优化点 #

• 可以先把硬币数组按面额从大到小排序，优先选大面额硬币，能更快找到较优的初始解，让剪枝逻辑触发更早，减少递归次数
• 如果只需要最少硬币数不需要具体组合，可以不用存路径列表，直接传当前路径长度做参数即可，进一步降低内存开销

内容的提问来源于stack exchange，提问作者Mar