递归更改：如何修改算法以打印所有组合？

我有一个算法递归地以下列方式进行更改：

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

但是，我想在成功返回时添加存储或打印每个组合的function。 我有点困难，围绕着如何做到这一点。 原始算法非常简单，但现在我很沮丧。 有什么建议么？

CB

Answer 1

在没有深入了解代码细节的情况下，一种模式是在参数中为结果携带一个可变容器

 public static int makeChange(int amount, int currentCoin, Listresults) { // .... if (valid_result) { results.add(result); makeChange(...); } // .... } 

并像这样调用函数

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

Answer 2

我不理解上面代码的逻辑或目的，但这是你可以如何存储然后打印每个组合。

 public class MakeChange { private static int[] availableCoins = { 1, 2, 5, 10, 20, 25, 50, 100 }; public static void main(String[] args) { Collection 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 makeChange( int amount, int currentCoin) { Collection results = new ArrayList(); makeChange(amount, currentCoin, results); return results; } public static int makeChange(int amount, int currentCoin, Collection 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; } } } 

Answer 3

我使用了以下内容：

 /** * 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 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 copyOfCoinsUsed = new ArrayList(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; }