硬币兑换问题-回溯的蛮力解决方案，但如何获得硬币

Question

我有一个带回溯的蛮力解决方案来解决硬币兑换问题。目前我得到了可以使用的最低数量的硬币。但是，我怎么能同时归还实际使用的硬币呢？例如，如果金额是100，那么我想返回[25，25，25，25]。

我当前的代码如下：

public class Solution {
public static void main(String[] args) {
Solution s = new Solution();
int coinChange = s.coinChange(0, new int[] { 1, 25, 50 }, 100);
System.out.println(coinChange);
}
public int coinChange(int idx, int[] coins, int amount) {
if (amount == 0){
return 0;
}
if (idx < coins.length && amount > 0) {
int maxVal = amount / coins[idx];
int minCost = Integer.MAX_VALUE;
for (int x = 0; x <= maxVal; x++) {
if (amount >= x * coins[idx]) {
int res = coinChange(idx + 1, coins, amount - x * coins[idx]);
if (res != -1)
minCost = Math.min(minCost, res + x);
}
}
return (minCost == Integer.MAX_VALUE) ? -1 : minCost;
}
return -1;
}
}

Answer 1

首先，我建议使用准确的变量名。这将使每个人，包括你自己，更容易理解算法的工作原理。你当前的数组"coins"不是一个硬币列表，而是一个可用面额的列表，所以它应该命名为"面额"或"可用面额"或类似的名称。您称之为"金额"的变量是剩余金额，因此应将其命名为"剩余"或amount_remaining。

要存储到目前为止使用的硬币列表，您可以使用堆栈，也可以只使用像堆栈一样处理的列表。例如，您可以使用整数的ArrayList。每次您拨打coinChange时，请在拨打电话前将所选硬币的面额(面额[idx](添加到您的列表中。每次返回-1(失败(时，在返回之前删除列表中的最后一项(如果有(。当达到成功条件(amount_remaining==0(时，硬币列表将包含所使用的硬币。

更正：由于coinChange在循环中被多次调用，因此每次调用后都必须弹出堆栈，并在确定最佳最小值后再次推回。所以，它应该是这样的：

int best_coin = 0;
for (int x = 0; x <= maxVal; x++) {
if (amount >= x * coins[idx]) {
<<<<<< PUSH GOES HERE
int res = coinChange(idx + 1, coins, amount - x * coins[idx]);
<<<<<< POP GOES HERE
if (res == -1){ 
// failed to find valid combination of coins
} else {
if( minCost < res + x ){
// do nothing
} else { // update minimum
minCost = res + x;
best_coin = coins[idx];
}
}
}
<<<<<< PUSH BEST COIN
return (minCost == Integer.MAX_VALUE) ? -1 : minCost;