# Coin problem through brute force

I have some code that will brute force solve the following problem:

Given a set of x coins and a target sum to reach, what is the fewest number of coins required to reach that target?

The code so far:

import java.util.ArrayList;
import java.util.Arrays;

public class coinsSum {
public static int min = Integer.MAX_VALUE;
public static int[] combination;
public static final int TARGET = 59;

public static void main(String[] args) {
long start = System.nanoTime();

int[] validCoins = new int[] {1, 2, 5, 10, 20};
Arrays.sort(validCoins);
int len = validCoins.length;

ArrayList<Integer> maxList = new ArrayList<Integer>();
for(int c : validCoins) {
}

int[] max = new int[len];
for(int i = 0; i < len; i++) {
max[i] = maxList.get(i).intValue();
}

permutations(new int[len], max, validCoins, 0); // bread&butter

if(min != Integer.MAX_VALUE) {
System.out.println();
System.out.println("The combination " + Arrays.toString(combination) + " uses " + min + " coins to make the target of: " + TARGET);
} else {
System.out.println("The target was not reachable using these coins");
}

System.out.println("TOOK: " + (System.nanoTime() - start) / 1000000 + "ms");
}

public static void permutations(int[] workspace, int[] choices, int[] coins, int pos) {
if(pos == workspace.length) {
int sum = 0, coinCount = 0;
System.out.println("TRYING " + Arrays.toString(workspace));
for(int a = 0; a < coins.length; a++) {
sum += workspace[a] * coins[a];
coinCount += workspace[a];
}
if(sum == TARGET) {
// System.out.println(Arrays.toString(n)); //valid combinations
if(coinCount < min) {
min = coinCount;
combination = workspace;
System.out.println(Arrays.toString(combination)+" uses " + min + " coins");
}
}
return;
}
for(int i = 0; i <= choices[pos]; i++) {
workspace[pos] = i;
permutations(workspace, choices, coins, pos + 1);
}
}
}


This solution uses recursion. Is there any way to compute combinations in Java using loops?

What other improvements can be made to the algorithm?

Your code is quite complicated. What makes it so complicated is that you have recursive calls interacting with global objects. This makes it almost impossible to understand what the state is at a given point.

When you write an algorithm in a recursive way, your goal should be to make the (smallest amount of) information go in one direction only through the method parameters (and no global state whatsoever) and to use return values to give the answer back.

This being said, let's try to see how to make this work.

This idea is quite simple here:

If I have to reach 59 with 1, 2, 5, 10, 20, I can try to take 0 time 20 and see how I can reach 59 with 1, 2, 5, 10. I can also try to take 1 time 20 and see how I can reach the remaining 39 with 1, 2, 5, 10. I can also try to take 2 times 20 and see how I can reach 19 with the remaining 1, 2, 5, 10.

I've reduced solving the problem to the resolution of smaller (because we have a smaller number of coins) problems. The question is "when should I stop ?". If you have reached the target, you can stop. If you have no coin left to try, you can stop;

Once expressing this with code, you can write:

import java.util.ArrayList;
import java.util.Arrays;

public class coinsSum {
public static final int TARGET = 59;

public static void main(String[] args) {
long start = System.nanoTime();

int[] validCoins = new int[] {1, 2, 5, 10, 20};
Arrays.sort(validCoins);

int min = permutations(TARGET, validCoins);
System.out.println("TOOK: " + (System.nanoTime() - start) / 1000000 + "ms to find " + min);
}

public static int permutations(int target, int[] coins) {
return permutations(target, coins, coins.length);
}

public static int permutations(int target, int[] coins, int array_size) {
System.out.println("TRYING " + target + " with " + array_size + " different coins");
assert target >= 0;
assert array_size >= 0;
assert array_size <= coins.length;
if (target==0) // target is reached (in 0 coin)
return 0;
if (array_size == 0) // no more coins to reach a positive target
return -1;
array_size--;
int coin = coins[array_size]; // let's consider the biggest coin
int nb = target/coin; // and check how many times it fits in the target
int sol = -1; // we haven't found a solution so far (Integer.MAX_VALUE would be another way to do this)
for (int i = 0; i <= nb; i++) // let's try all possible values
{
// to check if we can reach the target with the other coins
int sol_cand = permutations(target - i * coin, coins, array_size);
if (sol_cand >= 0) // if we did
{
if (sol == -1 || sol_cand + i < sol) // and the new solution is better
sol = sol_cand + i; // then we are happy
}
}
return sol;
}
}


Now, you can try to add optimisations. A simple optimisation is to say that if you can reach the current target with the biggest coin, there's no need to go any further because you'll need more coins if you use smaller coins.

    int coin = coins[array_size]; // let's consider the biggest coin
int nb = target/coin; // and check how many times it fits in the target
if (nb * coin == target) // if it fits an exact number of time, we won't beat this
return nb;


This makes the code 70 times faster on the example. (If you do so, the check that target == 0 is not relevant anymore because we'll always have target > 0).

Also, not a particular optimisation but if you want to use with Integer.MAX_VALUE just like you used to, you can rewrite the loop:

    int sol = Integer.MAX_VALUE; // we haven't found a solution so far (Integer.MAX_VALUE would be another way to do this)
for (int i = 0; i <= nb; i++) // let's try all possible values
{
sol = Math.min(sol, i + permutations(target - i * coin, coins, array_size));
}


This is as simple as it gets. Then, you can write unit tests to check that your code behaves the way you want. Finally, if you want to, you can consider various optimisations: using a cache to avoid computing the same thing multiple times, add conditions to stop the loop earlier, etc.

• Good answer, what is sol_cand short for? Dec 30, 2014 at 17:41
• It stands for "candidate solution". Not the greatest name now that I think about it :-P Dec 30, 2014 at 17:43