Making change recursively: How do I modify my algorithm to print all combinations?

Posted by cb on Stack Overflow See other posts from Stack Overflow or by cb
Published on 2010-02-05T19:30:58Z Indexed on 2010/03/16 13:06 UTC
Read the original article Hit count: 285

Filed under:
|
|

I have an algorithm that recursively makes change in the following manner:

public static int makeChange(int amount, int currentCoin) {

        //if amount = zero, we are at the bottom of a successful recursion
        if (amount == 0){

            //return 1 to add this successful solution
            return 1;           

            //check to see if we went too far
        }else if(amount < 0){

            //don't count this try if we went too far
            return 0;

            //if we have exhausted our list of coin values
        }else if(currentCoin < 0){              

            return 0;

        }else{  

            int firstWay = makeChange(amount, currentCoin-1);
            int secondWay = makeChange(amount - availableCoins[currentCoin], currentCoin);

            return firstWay + secondWay;            
        }       
}   

However, I'd like to add the capability to store or print each combination as they successfully return. I'm having a bit of a hard time wrapping my head around how to do this. The original algorithm was pretty easy, but now I am frustrated. Any suggestions?

CB

© Stack Overflow or respective owner

Related posts about java

Related posts about algorithm-design