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