递归地进行变化：如何修改我的算法以打印所有组合？

Question

我有一个递归算法，可以按照以下方式进行更改：

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;            
        }       
}   

然而，我希望增加能够存储或打印每个成功返回的组合的功能。但是，我有点难以理解如何实现这一点。原始算法很简单，但现在我感到沮丧。有什么建议吗？

CB

- cb.

Answer 1

不涉及您的代码细节，一种模式是在参数中携带一个可变容器来存储结果。

public static int makeChange(int amount, int currentCoin, List<Integer>results) {
     // ....
     if (valid_result) {
        results.add(result);
        makeChange(...);
     }
     // ....
}

并且像这样调用函数

List<Integer> results = new LinkedList<Integer>();
makeChange(amount, currentCoin, results);
// after makeChange has executed your results are saved in the variable "results"

- Otto Allmendinger

Answer 2

我使用了以下内容：

/**
     * This is a recursive method that calculates and displays the combinations of the coins included in
     * coinAmounts that sum to amountToBeChanged.
     * 
     * @param coinsUsed is a list of each coin used so far in the total.  If this branch is successful, we will add another coin on it.
     * @param largestCoinUsed is used in the recursion to indicate at which coin we should start trying to add additional ones.
     * @param amountSoFar is used in the recursion to indicate what sum we are currently at.
     * @param amountToChange is the original amount that we are making change for.
     * @return the number of successful attempts that this branch has calculated.
     */private static int change(List<Integer> coinsUsed, Integer currentCoin, Integer amountSoFar, Integer amountToChange)
    {
        //if last added coin took us to the correct sum, we have a winner!
        if (amountSoFar == amountToChange)
        {
            //output 
            System.out.print("Change for "+amountToChange+" = ");

            //run through the list of coins that we have and display each.
            for(Integer count: coinsUsed){

                System.out.print(count + " ");
            }
            System.out.println();       

            //pass this back to be tallied
            return 1;
        }

        /*
         * Check to see if we overshot the amountToBeChanged
         */
        if (amountSoFar > amountToChange)
        {
            //this branch was unsuccessful
            return  0;
        }

        //this holds the sum of the branches that we send below it
        int successes=0;

        // Pass through each coin to be used
        for (Integer coin:coinAmounts)
        {
            //we only want to work on currentCoin and the coins after it
            if (coin >= currentCoin)
            {
                //copy the list so we can branch from it
                List<Integer> copyOfCoinsUsed = new ArrayList<Integer>(coinsUsed);

                //add on one of our current coins
                copyOfCoinsUsed.add(coin);

                //branch and then collect successful attempts
                successes += change(copyOfCoinsUsed, coin, amountSoFar + coin, amountToChange);
            }
        }

        //pass back the current
        return successes;

    } 

- cb.

Answer 3

我不理解上面代码的逻辑或目的，但这是如何将每个组合存储并打印出来的方法。

public class MakeChange {

    private static int[] availableCoins = { 
        1, 2, 5, 10, 20, 25, 50, 100 };

    public static void main(String[] args) {
        Collection<CombinationResult> results = makeChange(5, 7);
        for (CombinationResult r : results) {
            System.out.println(
                    "firstWay=" + r.getFirstWay() + " : secondWay="
                    + r.getSecondWay() + " --- Sum=" + r.getSum());
        }
    }

    public static class CombinationResult {

        int firstWay;

        int secondWay;

        CombinationResult(int firstWay, int secondWay) {
            this.firstWay = firstWay;
            this.secondWay = secondWay;
        }

        public int getFirstWay() {
            return this.firstWay;
        }

        public int getSecondWay() {
            return this.secondWay;
        }

        public int getSum() {
            return this.firstWay + this.secondWay;
        }

        public boolean equals(Object o) {
            boolean flag = false;
            if (o instanceof CombinationResult) {
                CombinationResult r = (CombinationResult) o;
                flag = this.firstWay == r.firstWay
                        && this.secondWay == r.secondWay;
            }
            return flag;
        }

        public int hashCode() {
            return this.firstWay + this.secondWay;
        }

    }

    public static Collection<CombinationResult> makeChange(
            int amount, int currentCoin) {
        Collection<CombinationResult> results = 
            new ArrayList<CombinationResult>();
        makeChange(amount, currentCoin, results);
        return results;
    }

    public static int makeChange(int amount, int currentCoin,
            Collection<CombinationResult> results) {
        // 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, results);
            int secondWay = makeChange(
                amount - availableCoins[currentCoin],
                currentCoin, results);
            CombinationResult resultEntry = new CombinationResult(
                firstWay, secondWay);
            results.add(resultEntry);
            return firstWay + secondWay;
        }
    }

}

- Gladwin Burboz