java - 硬币找零 - 所有解决方案递归 - Java

Question

我正在尝试寻找 coin change problem 的所有可能的解决方案.

示例:我有硬币 1 和 2，我想兑换 6。

正确解: [1,1,1,1,1,1], [2,1,1,1,1,0], [2,2,1,1, 0,0], ...

我的代码: [1,1,1,1,1,1], [1,1,1,1,0,0], [1,1,0,0, 0,0], ...

最后一行还删除了我的参数“coinsSoFar”，我不明白为什么。当我调试时，它将 temp 设置为 [0,0,0,0,0,0] 并且 coinSoFar 设置为 [0,0,0,0,0,0]，它应该保持在 [2,0,0,0, 0,0]。

非常感谢您的帮助。(clearArray:所有数字设置为0；addToArray:用数字替换前0)

    public static void makeChange(int amount, int startCoinIndex, int[] coinsSoFar) {

    if (amount == 0) {
        System.out.println(Arrays.toString(coinsSoFar));
    }

    if (startCoinIndex == coinSet.length || amount < 0) {return;}

    for (int i = 0; i * coinSet[startCoinIndex] <= amount; i++) {

        int[] temp = coinsSoFar;

        for (int j = 0; j < i; j++) {
            addToArray(temp, coinSet[startCoinIndex]);
        }

        makeChange(amount - i * coinSet[startCoinIndex], startCoinIndex+1, temp);
        clearArray(temp);  // this line also clears coinsSoFar. Why?

    }
}

Answer 1

当你这样做

int[] temp = coinsSoFar;

您正在设置 temp 以引用与 coinsSoFar 相同的数组。因此，您对 temp 所做的任何操作现在都会影响 coinsSoFar。

如果您想让 temp 引用 coinsSoFar 的副本，请执行以下操作:

int[] temp = Arrays.copyOf(coinsSoFar, coinsSoFar.length);
//  OR, if you prefer
int[] temp = new int[coinsSoFar.length];
System.arraycopy(coinsSoFar, 0, temp, 0, coinsSoFar.length);