回溯法在LeetCode #322(零钱兑换)出错却在#78(子集)正确的原因
LeetCode #322 零钱兑换
给定一个表示不同面额硬币的整数数组coins和一个表示总金额的整数amount。返回凑成总金额所需的最少硬币个数。如果无法凑出该金额，返回-1。你可以认为每种硬币的数量是无限的。
示例1：
输入：coins = [1,2,5], amount = 11
输出：3
解释：11 = 5 + 5 + 1
import java.util.Arrays; import java.util.ArrayList; class Solution { static final int MAX_INF = Integer.MAX_VALUE; public int coinChange(int[] coins, int amount) { int n = coins.length; int[][] dp = new int[n + 1][amount + 1]; for (int[] arr : dp) { Arrays.fill(arr, -1); } int res = minCoinsReq(coins, amount, n,new ArrayList<Integer>(), dp); if (res == MAX_INF -1) { return -1; } return res; } public int minCoinsReq(int[] coins, int amount, int n, ArrayList<Integer> curCoinsList, int[][] dp){ if(amount ==0){ return curCoinsList.size(); } if(n==0){ return MAX_INF-1; } if(dp[n][amount]!=-1 ){ return dp[n][amount]; } if(coins[n-1]<=amount){ int coinAtIdxNotIncluded = minCoinsReq(coins,amount,n-1,curCoinsList,dp); curCoinsList.add(coins[n-1];) int coinAtIdxIncluded = minCoinsReq(coins,amount-coins[n-1],n, curCoinsList,dp); curCoinsList.remove(curCoinsList.size()-1); return dp[n][amount]= Math.min(coinAtIdxIncluded,coinAtIdxNotIncluded); }else { return dp[n][amount]= minCoinsReq(coins,amount,n-1, curCoinsList,dp); } } }
LeetCode #78 子集
给定一个元素互不相同的整数数组nums，返回其所有可能的子集（幂集）。解集不能包含重复的子集，返回顺序任意。
示例1：
输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
import java.util.List; import java.util.ArrayList; import java.util.Set; import java.util.HashSet; class Solution { public List<List<Integer>> subsets(int[] nums) { Set<List<Integer>> result = new HashSet<>(); addSubsetsRec(nums, result, new ArrayList<Integer>(), 0); return new ArrayList<>(result); } public void addSubsetsRec(int[] nums, Set<List<Integer>> result, List<Integer> currentList, int idx) { if (idx == nums.length) { result.add(new ArrayList<>(currentList)); return; } // Exclude current element addSubsetsRec(nums, result, currentList, idx + 1); // Include current element currentList.add(nums[idx]); addSubsetsRec(nums, result, currentList, idx + 1); // Backtrack to remove the recently added element currentList.remove(currentList.size() - 1); } }
技术问询
为何使用回溯法实现上述两个问题时，在LeetCode #322（零钱兑换）问题中得到错误结果，而在LeetCode #78（子集）问题中结果正确？
问题分析与解答
核心差异：回溯状态管理的逻辑适配性
子集问题（#78）的回溯逻辑是遍历所有元素的选择组合，每次递归到终点时，都会把当前currentList的副本存入结果集。虽然递归过程中共享同一个currentList，但回溯时会恢复列表状态（移除刚添加的元素），且每个分支的结果都是独立的副本，不同分支之间不会互相干扰，因此能正确生成所有子集。
而零钱兑换问题（#322）的代码存在三个关键问题，导致结果错误：
共享列表的状态污染与记忆化冲突
递归中传递的curCoinsList是同一个ArrayList引用，同时还使用dp数组做记忆化。当计算选择当前硬币的分支时，会给curCoinsList添加元素，递归返回后再移除，但dp[n][amount]存储的是该分支返回的curCoinsList.size()——这个值依赖于当时的列表状态。后续其他递归分支访问同一个dp[n][amount]时，列表状态已经被修改，拿到的记忆化值完全错误。语法错误
代码中curCoinsList.add(coins[n-1];)这一行多了一个分号，正确写法应为curCoinsList.add(coins[n-1]);，这个错误会直接导致编译失败，无法运行出正确结果。记忆化设计逻辑错误
零钱兑换的dp[n][amount]应该直接存储“用前n种硬币凑成amount的最小硬币数”，不需要依赖外部共享列表统计数量。正确的做法是：选择当前硬币时，递归结果加1（代表加上当前这枚硬币）；不选则直接取递归结果，最后取两者最小值存入dp。
修正后的零钱兑换递归实现（参考）
去掉共享列表，直接通过递归返回值计算最小硬币数：
import java.util.Arrays; class Solution { static final int MAX_INF = Integer.MAX_VALUE; public int coinChange(int[] coins, int amount) { int n = coins.length; int[][] dp = new int[n + 1][amount + 1]; for (int[] arr : dp) { Arrays.fill(arr, -1); } int res = minCoinsReq(coins, amount, n, dp); return res == MAX_INF - 1 ? -1 : res; } public int minCoinsReq(int[] coins, int amount, int n, int[][] dp) { if (amount == 0) { return 0; // 凑成0元需要0个硬币 } if (n == 0) { return MAX_INF - 1; // 无硬币可选，无法凑成 } if (dp[n][amount] != -1) { return dp[n][amount]; } if (coins[n-1] <= amount) { // 选择当前硬币：递归结果+1 int include = minCoinsReq(coins, amount - coins[n-1], n, dp); if (include != MAX_INF - 1) { include += 1; } // 不选择当前硬币 int exclude = minCoinsReq(coins, amount, n-1, dp); return dp[n][amount] = Math.min(include, exclude); } else { // 硬币面额超过金额，只能不选 return dp[n][amount] = minCoinsReq(coins, amount, n-1, dp); } } }
内容的提问来源于stack exchange，提问作者Ashna kohli
