Java BackTracking with coins

Question

Good afternoon,

I am currently working on a program that should use a backtrack algorithm to find a solution for the total number of coins it will take to reach a certain amount.

The basic layout of the program is this

User is prompted for an amount (ie. 123)
 int amount = input.nextInt();

User is prompted for number of coins (ie. 6)
 int numCoins = input.nextInt();

User is prompted for coin values (ie. 2, 4, 32, 51, 82)
 int[] array = new array[] {2, 4, 32, 51, 82};

From this information, I am to develop a backtracking algorithm to output a solution.
I have tried to look up backtracking information to no real avail. It all seems pretty unclear to me where exactly I am suppose to start with the algorithm.

Any help is appreciated.

EDIT

This is currently what I have been working on... It is currently not working

public class coins
{

public static int[] coinValues;
public static int currentAmount = 0;

public static void main(String[] args)
{
    ArrayList<Integer> temp = new ArrayList<>();
    Scanner input = new Scanner(System.in);

    System.out.println("Please enter the amount: ");
    int amount = input.nextInt();

    System.out.println("Please enter the number of coins: ");
    int numCoins = input.nextInt();
    coinValues = new int[numCoins];

    for (int i = 0; i < numCoins; i++)
    {
        System.out.println("Please enter coin value of " + i + " :");
        int value = input.nextInt();
        coinValues[i] = value;
    }

    for (int i = 0; i < coinValues.length; i++)
    {
        System.out.print("Coin Value: " + i + " " + coinValues[i] + "\n");
    }

    tryThis(temp, amount);

    for (int i = 0; i < temp.size(); i++)
    {
        System.out.println(temp.get(i) + " " + " ");
    }
}

public static ArrayList<Integer> tryThis(ArrayList<Integer> list, int amount)
{
    if (isValid(list, amount) == false)
    {
        while (amount > currentAmount && (amount > 0))
        {
            for (int i = 0; i < coinValues.length; i++)
            {
                for (int k = coinValues.length - 1; k > 0; k--)
                {
                    list.add(coinValues[k]);
                    int currentCoin = list.get(i);


                    if (amount > currentAmount)
                    {
                        amount = amount - currentCoin;
                        System.out.println("Amount: " + amount);
                    }

                    tryThis(list, amount);
                }
            }
        }
    }


    return new ArrayList<>();
}

public static boolean isValid(ArrayList list, int amount)
{
    boolean keepGoing = true;
    if (amount > currentAmount)
    {
        return keepGoing = false;
    }
    else
    {
        return keepGoing;
    }
}
}

Regards, Mike

Answer 1

Your basic algorithm will look like this:

For a given amount
  For each coin type
    Add the coin to a set
    If the set exceeds the amount, discard that set.
    If the set contains more coins than it should, discard the set.
    If the set equals the amount, add that set to the set of valid possibilities.
    Otherwise run the algorithm on each set you've created.

With backtracking you typically hold onto the amount left to allocate with each iteration of the algorithm (hence 'backtrack' because you're trying to find a solution for smaller and smaller amounts). For instance, lets say I'm looking for $0.07 using dimes, nickels and pennies:

I start with empty sets.
I add a dime to one set. 
I subtract '10' from my amount.
This is a negative number, so I discard that set: it is invalid.
I add a nickel to another (empty) set.
I subtract '5' from my amount.
This equals 2; so I'll have to keep working on this set. 
Now I'm working with sets that already include one nickel.
I add a dime to one set.
I subtract '10' from my amount.
This is a negative number, so I discard that set: it is invalid.
I repeat this with a nickel; I discard this possibility because (2 - 5) is also negative.
I repeat this with a penny; this is valid but I still have 1 left.
I repeat this whole process again with a starting set of one nickel and one penny, 
  again discarding a dime and nickel, 
  and finally adding a penny to reach an amount of 0: this is a valid set.
Now I go back to empty sets and repeat starting with a nickel, then pennies.

Note that this algorithm should produce multiple results:

[nickel, penny, penny]
[penny, nickel, penny]
[penny, penny, nickel]
[penny, penny, penny, penny, penny, penny, penny]

Functional languages are natural fits for this sort of recursive work, but you can replicate this algorithm in any language.

This would be an example of implemented code, not including elegant pruning of duplicates:

import java.util.*;

public class Backtrack {

  private static List<List<Integer>> findSets(int amount, List<Integer> coinTypes, int numberOfCoins) {
    List<List<Integer>> results = new ArrayList<List<Integer>>();

    for (Integer coin : coinTypes) {
      List<Integer> result = new ArrayList<Integer>();
      result.add(coin);
      int currentAmount = amount - coin;
      if (currentAmount >=0) { //only continue if we haven't overshot
        if (currentAmount == 0) {
          results.add(result);//this is a valid solution, add it to result set
        } else {//still some value to make up
          if ((numberOfCoins - 1) > 0){//otherwise we shouldn't recurse
            List<List<Integer>> recurseResults = findSets(currentAmount, coinTypes, (numberOfCoins - 1));
            for (List<Integer> recurseResult : recurseResults) {//Have to add this layer's coin in to each result
              recurseResult.add(coin);
            }
            results.addAll(recurseResults);
          }
        }
      }
    }

    return results;
  }

  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int amount = 7;
    List<Integer> coinTypes = new ArrayList<Integer>();
    coinTypes.add(Integer.valueOf(1));
    coinTypes.add(Integer.valueOf(5));
    coinTypes.add(Integer.valueOf(10));
    int numberOfCoins = 3;

    List<List<Integer>> results = findSets(amount, coinTypes, numberOfCoins);
    System.out.println("Number of results: " + results.size());
    for (List<Integer> result : results) {
      System.out.print("Result: ");
      for (Integer coin: result) {
        System.out.println(result.toString() + ",");
      }
    }
  }
}