java - 如果您只能投资 10 美元增量，则输出投资 10 只股票的方式总数

Question

我在美国运通公司收到了这个面试问题，虽然想象答案非常简单，但我很难弄清楚如何实际生成它。

有人有通过分而治之解决此类组合问题的好方法吗？

示例输出:

这些数组代表 10 只不同的股票以及您在每只股票上投资的 100 美元的金额。

(100, 0, 0, 0, 0, 0, 0, 0, 0, 0), (0, 100, 0, 0, 0, 0, 0, 0, 0, 0) 等等

(90, 10, 0, 0, 0, 0, 0, 0, 0, 0), (90, 0, 10, 0, 0 ,0, 0, 0, 0 ,0) 等

对于每一种可能的组合。

Answer 1

您可以使用递归。

在每支股票 i 上，您都有剩余金额可供消费，并且您可以在任何地方以 10 为增量最多消费该金额。对于最后一家商店，您必须花掉剩余金额。

我会在每次组合后调用监听器、回调或打印数组。

public static void printCombinations(int stocks, int cash, int cashMultiple) {
    int[] amounts = new int[stocks];
    printCombinations(amounts, 0, cash, cashMultiple);
}

public static void printCombinations(int[] amounts, int n, int cash, int cashMultiple) {
    if (n == amounts.length-1) {
        amounts[n] = cash;
        System.out.println(Arrays.toString(amounts));
        return;
    }
    for (int i = 0; i <= cash ; i += cashMultiple) {
        amounts[n] = i;
        printCombinations(amounts, n+1, cash - i, cashMultiples);
    }