import java.util.HashMap;

/**

* given an array of different coin sizes and a target amount you want to break down

* in how many different ways can you break it down into coins?

* Also every coin can only be used once

* <p>

* this solution assumes coin values are whole integers

*/

// using every coin once - how many different sets of coins do you have?

public class CoinChange {

private static int howManySets(int[] arr, int target, HashMap<Integer, Integer> memo, int index) {

// if we have done this calculation before just return the result

if (memo.containsKey(target))

return memo.get(target);

if (index >= arr.length && target != 0) {

return 0;

}

if (target - arr[index] >= 0) {

// possibilities if we choose to include this coin value

int possiblity1 = howManySets(arr, target - arr[index], memo, index + 1);

if (!memo.containsKey(target - arr[index]))

memo.put(target - arr[index], possiblity1);

// and possibilities if we chose to skip this coin

int possiblity2 = howManySets(arr, target, memo, index + 1);

if (!memo.containsKey(target))

memo.put(target, possiblity2);

return possiblity1 + possiblity2;

} else {

int possiblity2 = howManySets(arr, target, memo, index + 1);

if (!memo.containsKey(target))

memo.put(target, possiblity2);

return possiblity2;

}

}

public static void main(String[] args) {

//array of different coins we can use

int[] arr = {2, 4, 6, 10, 8};

int target = 12;

// key - what is the target

// value - how many sets

HashMap<Integer, Integer> memo = new HashMap<>();

//if the value is broken up and you are left with 0$ to break down -> there is only one possibility

memo.put(0, 1);

System.out.println(howManySets(arr, target, memo, 0));

}

}