maxomax
BAN USERHere is the code in Java. Tested with basic use cases. Please let me know if there are any bugs in this.
public static void findAllCombinationsOfDenominationsWhichAddsToX(int a[], int X){
findAllCombinationsOfDenominationsUtil(a, X, 0, 0, "");
}
public static void findAllCombinationsOfDenominationsUtil(int a[],
int X,
int current_index,
int current_sum,
String resultant_string ){
for(int i= current_index; i<a.length;i++ ){
if(current_sum+ a[i] == X){
//resultant_string = resultant_string + " , " + a[i];
System.out.println("These denominations can form the sum:"+
resultant_string + " "+a[i]);
return;
}
else if(current_sum + a[i] < X){
findAllCombinationsOfDenominationsUtil(a, X,
i+1, current_sum + a[i], resultant_string + " " + a[i]);
}
}
}
We can improve further with LinkedHashMap. We need not iterate the whole map. Remove the duplicate elements from the map as you see them. And, then the first entry of the map would be the answer. Here is the code:-
- maxomax October 20, 2015