爲什麼我的遞歸解決方案打印重複？

Question

的問題是：

編寫一個使用遞歸回溯找到所有方式使用便士（1分），鎳（5分），助攻（10美分），以供錢給定的量變化的靜態方法makeChange ，和宿舍（25美分）。例如，當變更37美分時，您可以使用：1美分，1美分和2美分; 3個硬幣和7個便士;或其他組合。

您的方法應該接受一個參數：進行更改的分的數量。你的方法的輸出應該是每種硬幣的所有組合的序列，加起來就是每行一個。例如，如果客戶端代碼包含以下調用：

System.out.println（「P N D Q」）;
System.out.println（「------------」）;
makeChange（28）;

產生應該是以下的總功率輸出：

PNDQ
------------
[3，0，0，1]
[3,1 2，0]
[3,3，1,0]
[3,5，0,0]
[8,0，2,0]
[8,2，1,0]
[8,4,0,0]
[13,1,1,0 ]
[13，3,0，0]
[18，0，1，0]
[18，2,0，0]
[23，1,0，0]
[28， 0，0，0]

我的解決辦法是保持對應四種面額的整數列表。一個單獨的方法處理列表中「硬幣」的總值。直到總和等於給定值，在該點它打印遞歸方法增加了每一幣值的「硬幣」的數量。不幸的是我的解決方案打印出每種可能的硬幣組合的許多重複。爲什麼？輸出的

public static void makeChange(int n) { 
    ArrayList<Integer> combos = new ArrayList<Integer>(); 
    combos.add(0); 
    combos.add(0); 
    combos.add(0); 
    combos.add(0); 
    System.out.println(" P N D Q"); 
    System.out.println("------------"); 
    makeChange(n, combos); 
} 

public static void makeChange(int n, ArrayList<Integer> combos) { 
    int sum = getSum(combos); 
    if (sum == n) { 
     System.out.println(combos.toString()); 
    } else { 
     for (int i = 0; i < combos.size(); i++) { 
     combos.set(i, combos.get(i) + 1); 
     if (getSum(combos) <= n) { 
      makeChange(n, combos); 
     } 
     combos.set(i, combos.get(i) - 1); 
     } 
    } 
} 

public static int getSum(ArrayList<Integer> combos) { 
    int sum = combos.get(0); 
    sum += 5 * combos.get(1); 
    sum += 10 * combos.get(2); 
    sum += 25 * combos.get(3); 
    return sum; 
} 

實施例：

呼叫makeChange（6）產生以下輸出：

PNDQ
------------
[6 ，0，0，0]
[1,1，0,0]
[1,1，0,0] < -------重複

P.S.這是不是分配作業，這是自願的做法

Answer 1

您的for循環將重置i變量爲零，每次您調用遞歸函數，這會導致重複的輸出。

你需要在這個變量傳遞作爲輸入參數：

public static void makeChange(int n) { 
    List<Integer> combos = new ArrayList<Integer>(); // you should declare as List, not ArrayList 
    combos.add(0); 
    combos.add(0); 
    combos.add(0); 
    combos.add(0); 
    System.out.println(" P N D Q"); 
    System.out.println("------------"); 
    makeChange(n, 0, combos); 
} 

public static void makeChange(int n, int i, List<Integer> combos) { 
    int sum = getSum(combos); 
    if (sum == n) { 
     System.out.println(combos.toString()); 
    } else { 
     while (i < combos.size()) { 
     combos.set(i, combos.get(i) + 1); 
     if (getSum(combos) <= n) { 
      makeChange(n, i, combos); 
     } 
     combos.set(i, combos.get(i) - 1); 
     ++i; 
     } 
    } 
} 

對於makeChange(28)，此輸出：

P N D Q 
------------ 
[28, 0, 0, 0] 
[23, 1, 0, 0] 
[18, 2, 0, 0] 
[18, 0, 1, 0] 
[13, 3, 0, 0] 
[13, 1, 1, 0] 
[8, 4, 0, 0] 
[8, 2, 1, 0] 
[8, 0, 2, 0] 
[3, 5, 0, 0] 
[3, 3, 1, 0] 
[3, 1, 2, 0] 
[3, 0, 0, 1] 

爲makeChange(6)，它輸出：

P N D Q 
------------ 
[6, 0, 0, 0] 
[1, 1, 0, 0] 

保持記住P < N < D <問：你以前的解決方案，是找到一個很好的P上之後再增加磷，這是沒有必要的

編輯 要反向輸出，你可以先寫輸出到一個列表，然後，當進程完成後，輸出列表：現在

public static void makeChange(int n) { 
    List<Integer> combos = new ArrayList<Integer>(); 
    List<String> output = new ArrayList<String>(); 
    combos.add(0); 
    combos.add(0); 
    combos.add(0); 
    combos.add(0); 
    System.out.println(" P N D Q"); 
    System.out.println("------------"); 
    makeChange(n, 0, combos, output); 
    for(String s: output) { 
     System.out.println(s); 
    } 
} 

public static void makeChange(int n, int i, List<Integer> combos, List<String> output) { 
    int sum = getSum(combos); 
    if (sum == n) { 
     output.add(0, combos.toString()); 
    } else { 
     while (i < combos.size()) { 
     combos.set(i, combos.get(i) + 1); 
     if (getSum(combos) <= n) { 
      makeChange(n, i, combos, output); 
     } 
     combos.set(i, combos.get(i) - 1); 
     ++i; 
     } 
    } 
} 

，爲makeChange(28)，輸出爲：

P N D Q 
------------ 
[3, 0, 0, 1] 
[3, 1, 2, 0] 
[3, 3, 1, 0] 
[3, 5, 0, 0] 
[8, 0, 2, 0] 
[8, 2, 1, 0] 
[8, 4, 0, 0] 
[13, 1, 1, 0] 
[13, 3, 0, 0] 
[18, 0, 1, 0] 
[18, 2, 0, 0] 
[23, 1, 0, 0] 
[28, 0, 0, 0]