以遞歸方式打印矩陣中的所有路徑

Question

我遇到了一個解決方案HERE。有人可以解釋這是如何工作的。特別是，我無法理解的一件事是遞歸調用。在其中一個new ArrayList<>(path)通過，而在其他簡單的path通過。爲什麼？解決方案之間正在工作。

public class Main { 

    public static void getPaths(int[][]A, int i, int j, ArrayList<Integer> path, ArrayList<ArrayList<Integer>> allPaths) { 
     int n = A.length; 
     if (i>=n || j>=n) return; 

     path.add(A[i][j]); 

     if (i==n-1 && j==n-1) { 
      allPaths.add(path); 
      return; 
     } 
     getPaths(A, i, j+1, new ArrayList<>(path), allPaths); 
     getPaths(A, i+1, j, path, allPaths); 
    } 

    public static void main(String[] args) { 
     ArrayList<ArrayList<Integer>> allPaths = new ArrayList<>(); 
     getPaths(new int[][] { {1,2,3},{4,5,6},{7,8,9}}, 0,0, new ArrayList<Integer>(), allPaths); 
     System.out.println(allPaths); 
    } 
} 

Answer 1

到目前爲止，路徑的副本被創建並在第一次遞歸調用中傳遞，以便可以將更多條目添加到路徑中。我們不需要在第二個電話中傳遞它，因爲第二個電話會添加任何條目，這些都是第一個電話路徑的一部分。

Answer 2

它們表示與當前路徑不同的兩條路徑。因此，新的ArrayList（路徑）用於在一個方向上創建當前路徑的副本，只傳遞路徑以完成另一個方向上的當前路徑。

基本上，因爲你想完成兩個不同的pahts，你不能使用當前的在同一個數組中插入兩個不同的路徑。因此，您在其中一個調用中傳遞副本，以便在不同的存儲區域中擁有該路徑，因此可以獨立計算在當前點分離的兩條路徑。