## Interview Question

**Country:**United States

1) Use recursion to get all combinations of coins (2^n) and hashmap to store unique sum values.

```
combination(sum,i)
if i == no of elements in array
//a particular combination of coins reached
H[sum] = sum
return
//include element i in the sum
combination(sum+A[i],i+1)
//do not include element i in the sum
combination(sum, i+1)
```

public class Coins

{

static public String[] aCoins = {"5","10","20","50"};

public static void main(String[] args)

{

Coins c = new Coins();

for(int i=0; i<aCoins.length; i++)

{

for(int j=i+1; j<aCoins.length; j++)

c.printComb(aCoins[i], aCoins[j], j+1);

}

}

public static void printComb(String a, String b, int i)

{

System.out.println(a + "+" + b);

String new1 = a+"+"+b;

while(i< aCoins.length)

{

printComb(new1, aCoins[i], i+1);

i = i+1;

}

}

}

Define a hashmap H for all possible sums.

assume coin values are stored in an array A,

- samuel February 22, 2014