My assignment is to find a way to display all possible ways of giving back change for a predetermined value, the values being scanned in from a `txt`

file. This must be accomplished by **Recursive Backtracking** otherwise my solution will not be given credit. I will be honest in saying I am completely lost on how to code in the appropriate algorithm. All I know is that the algorithm works something like this:

```
start with empty sets.
add a dime to one set.
subtract '10' from my amount.
This is a negative number, so I discard that set: it is invalid.
add a nickel to another (empty) set.
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.
add a dime to one set.
subtract '10' from my amount.
This is a negative number, so I discard that set: it is invalid.
repeat this with a nickel; I discard this possibility because (2 - 5) is also negative.
repeat this with a penny; this is valid but I still have 1 left.
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.
```

The issue is I haven't the slightest clue on how or where to begin, only that that has to be accomplished, or if any other solutions are apparent.

This is my code thus far:

**UPDATED**

```
import java.io.*;
import java.util.*;
import java.lang.*;
public class homework5 {
public static int penny = 1;
public static int nickle = 5;
public static int dime = 10;
public static int quarter = 25;
public static int halfDollar = 50;
public static int dollar = 100;
public static int change;
public static void main(String[] args) throws FileNotFoundException {
ArrayList<Integer> coinTypes = new ArrayList<Integer>();
Integer i;
File f = new File (args[0]);
Scanner input = new Scanner(f);
input.nextLine();
while(input.hasNextInt()) {
i = input.nextInt();
coinTypes.add(i);
}
change = coinTypes.get(coinTypes.size()-1);
coinTypes.remove(coinTypes.size()-1);
System.out.println("Found change"); //used for debugging
System.out.println("Change: " + change);
System.out.println(coinTypes);
}
boolean findChange(int change, List<Integer> coinTypes,
List<Integer> answerCoins) {
if(change == 0) {
return true;
}
if(change < 0) {
return false;
} else {
for(Integer coin : coinTypes) {
if(findChange(change - coin, coinTypes, answerCoins)){
answerCoins.add(coin);
return true;
}
}
List<Integer> answer = new ArrayList<Integer>();
boolean canFindChange = findChange(change, coinTypes, answer);
if(canFindChange) {
System.out.println(answer);
} else { System.out.println("No change found");
}
return false;
}
}
```

Here is the input file that I scan in

`java homework5 hwk5sample1.txt`

```
// Coins available in the USA, given in cents. Change for $1.43?
1 5 10 25 50 100
143
```

**OUTPUT**

```
Found change
Change: 143
[1, 5, 10, 25, 50, 100]
```

So using the numbers in my `coinTypes`

`ArrayList`

, I need a generic code algorithm to show all possible ways of receiving, for example, 143 ($1.43) back in change using the coins in the file with all pennies being the last way to show it.

Please do not think I want you to write me the algorithm, I am simply wanting help writing one otherwise I will learn nothing. Thank you all for any answers or help you can give it means a lot to me! Please let me know if i missed anything or you need more info