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

Question

我正在研究一个函数，它使用递归调用将给定的输入分解为面额。

在每一步，它都会递归成两个变体：

1. 继续使用当前硬币：将其添加到列表中并递归。

2. 切换到下一个硬币：增加硬币位置并递归。

除了在剩余 == 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

您必须添加return coins;at 和 ofchange方法，但您可以保留它的方式。返回和更改数组是一种代码味道，因为该方法既对对象进行操作（修改它）并返回结果。为了使其工作，您可以denomination按如下方式定义您的方法：public static List<Integer> denominations(int amount) {&nbsp; &nbsp;List<Integer> result = new ArrayList<Integer>();&nbsp; &nbsp;change(amount, result, 0);&nbsp; &nbsp;return result;}编辑：该列表是空的，因为它唯一改变的地方是这里：coins.add(DENOMINATIONS[pos]);change(remaining - DENOMINATIONS[pos], coins, pos);coins.remove(coins.size() - 1);添加和删除元素的位置。是你写的让它空了:)编辑2：我建议传递第二个对象，这将是您要返回的列表的副本，并且不会被修改。

Answer 2

您似乎认为 java 是通过引用传递的，这是不正确的。Java 方法是按值传递的。我已经更新了你的代码：改变方法：private static List<Integer> change(int remaining, List<Integer> coins, int pos) { // Updated method return type;&nbsp; &nbsp; if (pos < 0 || pos >= DENOMINATIONS.length) { // check if position is invalid&nbsp; &nbsp; &nbsp; &nbsp; return new ArrayList<>(); // return an empty list&nbsp; &nbsp; }&nbsp; &nbsp; if (remaining == DENOMINATIONS[pos]) { // check if remaining is equal to denominations[pos]&nbsp; &nbsp; &nbsp; &nbsp; coins.add(DENOMINATIONS[pos]); // add the denominations to the coins result&nbsp; &nbsp; &nbsp; &nbsp; return coins; // return the result&nbsp; &nbsp; } else if (remaining > DENOMINATIONS[pos]) { // check if remaining is greater than denominations[pos]&nbsp; &nbsp; &nbsp; &nbsp; coins.add(DENOMINATIONS[pos]);// add the possible denominations to the coins result&nbsp; &nbsp; &nbsp; &nbsp; remaining = remaining - DENOMINATIONS[pos]; // calculate the new remaining&nbsp; &nbsp; &nbsp; &nbsp; if (remaining >= DENOMINATIONS[pos]) { // check if remaining is greater than or equal to denominations[pos]&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return change(remaining, coins, pos); // stick to this position&nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return change(remaining, coins, pos + 1); // increment pos to go to the lower denominations&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; } else if (remaining < DENOMINATIONS[pos]) { // check if remaining is lesser than denominations[pos]&nbsp; &nbsp; &nbsp; &nbsp; if (coins.isEmpty()) { // if coins is empty then go to the next denomination&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return change(remaining, coins, pos + 1);&nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; coins.remove(coins.size() - 1); // remove the previous denomination&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return change(remaining + DENOMINATIONS[pos - 1], coins, pos); // go back to the previous remaining and // try this DENOMINATIONS[pos]&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return coins;}面额法：public static List<Integer> denominations(int amount) {&nbsp; &nbsp; return change(amount, new ArrayList<Integer>(), 0);}输入：13输出：[5, 5, 3]

Answer 3

change应该返回布尔值，表示是否已找到答案。所以change身体看起来像这样：if (remaining == 0) {&nbsp; return true;}...if (change(...)) return true;...return false;&nbsp; // It's last line of body