Ufdjrw

I'm working on a function which breaks down the given input into denominations using a recursive call.

At each step it recurses into two variants:

1. Continue with the current coin: Add it to the list and recurse.


2. Switch to the next coin: Increment coin pos and recurse.

In addition to printing out the combination of denominations captured in the list when remaining == 0, I intend to capture the value of that list and return it from the function.

Here's the code:

 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);
 

Output : [5, 5, 3]

You seems to assume that java is passed by reference which is not true. Java methods are passed by value.

I have updated your code:

change method:

private static List<Integer> change(int remaining, List<Integer> coins, int pos) pos >= DENOMINATIONS.length) // check if position is invalid
 return new ArrayList<>(); // return an empty list
 

 if (remaining == DENOMINATIONS[pos]) // check if remaining is equal to denominations[pos]
 coins.add(DENOMINATIONS[pos]); // add the denominations to the coins result
 return coins; // return the result
 else if (remaining > DENOMINATIONS[pos]) // check if remaining is greater than denominations[pos]
 coins.add(DENOMINATIONS[pos]);// add the possible denominations to the coins result
 remaining = remaining - DENOMINATIONS[pos]; // calculate the new remaining
 if (remaining >= DENOMINATIONS[pos]) // check if remaining is greater than or equal to denominations[pos]
 return change(remaining, coins, pos); // stick to this position
 else 
 return change(remaining, coins, pos + 1); // increment pos to go to the lower denominations
 
 else if (remaining < DENOMINATIONS[pos]) // check if remaining is lesser than denominations[pos]
 if (coins.isEmpty()) // if coins is empty then go to the next denomination
 return change(remaining, coins, pos + 1);
 else 
 coins.remove(coins.size() - 1); // remove the previous denomination
 return change(remaining + DENOMINATIONS[pos - 1], coins, pos); // go back to the previous remaining and // try this DENOMINATIONS[pos]
 
 
 return coins;

denominations method:

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

INPUT : 13
OUTPUT : [5, 5, 3]

You would have to add return coins; at the and of change method, but you can keep it the way you have it. Returning and changing an array is a code smell as the method both operates on object (modifies it) and returns a result.

To make it work, you can define your denomination method as follows:

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

Edit:

The list is empty because the only place it's changed is here:

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

Where an element is added and removed. It's what you have written that makes it empty:)

Edit2:

I would suggest passing around a second object, that would be a copy of the list you would like to return and is not modified.

change should return boolean that mean whether has been found an answer.

So change body looks like this:

if (remaining == 0) 
 return true;

...
if (change(...)) return true;
...
return false; // It's last line of body