java - 递归打印矩阵中的所有路径

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

创建到目前为止路径的副本并在第一个递归调用中传递，以便可以将更多条目添加到路径中。我们不需要在第二次调用中传递它，因为第二次调用所添加的任何条目都是第一次调用路径的一部分。