java - 硬币变化递归所有解决方案到不同的解决方案

Question

我是递归和回溯的新手。我知道在继续进行动态规划之前，我需要完全熟悉这些概念。我在下面编写了一个程序，可以帮助我找到给定数量 n 和无限数量硬币的所有可能组合。但是，我希望我的程序能给我不同的解决方案。我很难弄清楚如何做到这一点。

我在这里找到了资源:Coin Change它递归地使用自上而下的方法，然后使用以下公式修改它以给出不同的组合:count (s, n, total) = count (s, n, total-s[n]) + count(s, n-1 , 总计)

这表示我递归使用该值，然后递归排除该值并将硬币减 1。

我似乎无法理解这是如何工作的。我也可以肯定地说，每个人都很难在采访中当场想到这种技术。似乎有些人在某个时候不得不花费大量时间来解决这样的问题才能设计出这样的技术。

无论如何，对于如何将我的程序转换为打印不同的解决方案及其工作方式的帮助，我们将不胜感激。

public class Recursive {

    static int[] combo = new int[100];
    public static void main(String argv[]) {
        int n = 8;
        int[] amounts = {1, 5, 10};
        ways(n, amounts, combo, 0, 0, 0);
    }

    public static void  ways(int n, int[] amounts, int[] combo, int count, int sum, int index) {
        if(sum == n) {
            printArray(combo, index);
        }

        if(sum > n) {
            return;
        }


        for(int i=0;i<amounts.length;i++) {
            sum = sum + amounts[i];
            combo[index] = amounts[i];
            ways(n, amounts, combo, 0, sum, index + 1);
            sum = sum - amounts[i];
        }
    }

    public static void printArray(int[] combo, int index) {
        for(int i=0;i < index; i++) {
            System.out.print(combo[i] + " ");
        }
        System.out.println();
    }
}

使用纯递归穷举技术(下面的代码)，数量 {1, 2, 5} 和 N = 10 的非不同有效组合的实际数量是 128。

我的问题是，是否可以通过记忆化/动态规划改进穷举搜索。如果是这样，我如何修改下面的算法以包含此类技术。

Answer 1

简单的修改可以避免重复。

使用排序的数量数组。
循环的起始值应从 amounts 中排除以前的值。
我使用了 count 参数(似乎未使用)

 for(int i=count;i<amounts.length;i++) {
            sum = sum + amounts[i];
            combo[index] = amounts[i];
            ways(n, amounts, combo, i, sum, index + 1);
            sum = sum - amounts[i];
        }