sachinjainmail
BAN USERint MAX_NO_PICKS = Integer.MAX_VALUE;
//Pass any unsorted array, sum to check,no of picks pass 0, baseIndex pass 0
int getNumberOfPicks(int[] coinArr, int sum, int noOfPicks, int baseIndex){
if(noOfPicks+1 >= MAX_NO_PICKS && sum !=0){
return -1;
}else if(sum == 0){
MAX_NO_PICKS = noOfPicks;
return noOfPicks;
}
if(sum < 0) return -1;
if(baseIndex >= coinArr.length) return -1;
int tempSum = sum - coinArr[baseIndex];
int choosenPick = getNumberOfPicks(coinArr, tempSum, noOfPicks+1,baseIndex+1);
int notChoosenPick = getNumberOfPicks(coinArr, sum, noOfPicks,baseIndex+1);
//System.out.println(choosenPick +" "+notChoosenPick);
if(choosenPick == -1 && notChoosenPick == -1){
return -1;
}else if(choosenPick == -1){
return notChoosenPick;
}else if(notChoosenPick == -1){
return choosenPick;
}else{
if(choosenPick < notChoosenPick){
return choosenPick;
}else{
return notChoosenPick;
}
}
}
good solution, but can't we do it for unsorted array.
- sachinjainmail July 14, 2012
- sachinjainmail July 15, 2012