java - 将递归函数中的数据保存到列表

Question

我正在开发一个函数，该函数使用递归调用将给定输入分解为面额。

在每一步它递归成两个变体:

1. 继续当前硬币:将其添加到列表并递归。
2. 切换到下一个硬币:增加硬币位置并递归。

除了在 r​​emaining == 0 时打印出列表中捕获的面额组合外，我还打算捕获该列表的值并从函数中返回它。

代码如下:

    static final int[] DENOMINATIONS = {9,5,3};

    private static void change(int remaining, List<Integer> coins, int pos)

        if (remaining == 0) {

       // This correctly prints the desired output. 
       // I want to return that exact value from the function.
            System.out.println(coins); 

        } else {
            if (remaining >= DENOMINATIONS[pos]) {
                coins.add(DENOMINATIONS[pos]);
                another.addAll(coins);
                change(remaining - DENOMINATIONS[pos], coins, pos);
                coins.remove(coins.size() - 1);
            }
            if (pos + 1 < DENOMINATIONS.length) {
                change(remaining, coins, pos + 1);
            }
        }
    }


    public static List<Integer> denominations(int amount) {
        List<Integer> result = new ArrayList<Integer>();
        List<Integer> another = new ArrayList<Integer>();
        change(amount, result, another ,0);
        System.out.println(another.size());
        return another;
    }

    public static void main(String[] args) {
        List<Integer> list = denominations(13);
        System.out.println(list);
    }

输出:[5, 5, 3]

Answer 1

您必须在 change 方法的和处添加 return coins;，但您可以保持原样。返回和更改数组是一种代码味道，因为该方法既对对象进行操作(修改它)又返回结果。

要让它工作，您可以按如下方式定义您的denomination 方法:

public static List<Integer> denominations(int amount) {
   List<Integer> result = new ArrayList<Integer>();
   change(amount, result, 0);
   return result;
}

编辑:

列表是空的，因为它唯一改变的地方是这里:

coins.add(DENOMINATIONS[pos]);
change(remaining - DENOMINATIONS[pos], coins, pos);
coins.remove(coins.size() - 1);

添加和删除元素的位置。是你写的东西让它变空了:)

编辑2:

我建议传递第二个对象，它是您想要返回的列表的副本并且未被修改。