將內部遞歸方法的值傳遞給外部方法

Question

我從http://algorithms.tutorialhorizon.com/dynamic-programming-subset-sum-problem/找到了以下方法，它可以打印一個數組中的所有子集，並將它們相加成一定的數字。

我的代碼是完全我用來跟蹤遞歸調用打印語句：

public static void find(int[] A, int currSum, int index, int sum, 
     int[] solution, int tot) { 
    if (currSum == sum) { 
        tot +=1; 

     System.out.println("\nSum found "); 
     for (int i = 0; i < solution.length; i++) { 
      if (solution[i] == 1) { 
       System.out.print(" " + A[i]); 
      } 
     } 

    } else if (index == A.length) { 
       System.out.println("reached end"); 
     return; 
    } else { 
     solution[index] = 1;// select the element 
     currSum += A[index]; 
        System.out.println("incr " + A[index] + " "+ currSum + " "); 
     find(A, currSum, index + 1, sum, solution, tot); 
     currSum -= A[index]; 
        System.out.println("decr " + A[index] + " "+ currSum + " "); 
     solution[index] = 0;// do not select the element 
     find(A, currSum, index + 1, sum, solution, tot); 
    } 
    return;    
} 

我想修改的方法，以便它也打印在端到端解決方案的最終數目。 我知道這個問題已經在Stackoverflow上討論過了，我發現了一些有趣的解決方案。不過，我想知道是否有辦法修改這個特定的方法。 我的想法是創建一個整數「tot」，我在找到解決方案後立即添加1，然後將更新的值傳遞給每個遞歸調用。但最終的值將在內部遞歸調用中找到，我不知道如何將最終值傳遞給外部方法。

Answer 1

如果要在遞歸調用中獲得解決方案計數，最好的方法是在每個方法調用中傳遞可變引用。只要你得到一個解決方案，更新可變引用。這裏，可變引用很重要，因爲：

1. 原始類型很難通過遞歸調用傳播，因爲返回類型需要相應地進行維護和更新。
2. 不可變類型（如Integer）不會在遞歸調用中維護值。

解決方案：

1. 使用AtomicInteger
2. 使用原始的int陣列

雙方將能夠解決您的問題。您應該檢查數組的引用或長度，以使其不易出錯。下面給出的樣品：

private static void methodWithAtomicInteger(AtomicInteger i){ 
    i.incrementAndGet(); 
} 

private static void methodWithIntArray(int[] i){ 
    i[0]++; 
} 

public static void main(String[] args){ 
    AtomicInteger integer = new AtomicInteger(0); 
    System.out.println(integer); 
    methodWithAtomicInteger(integer); 
    System.out.println(integer); 

    int[] values = new int[]{0}; 
    System.out.println(values[0]); 
    methodWithIntArray(values); 
    System.out.println(values[0]); 
}