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

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

它们代表与当前路径不同的两条路径。因此，new ArrayList<>(path) 用于在一个方向上创建当前路径的副本，只传递路径以完成另一个方向上的当前路径。

本质上是因为要完成两个不同的路径，所以不能用当前的路径在同一个数组中插入两个不同的路径。因此，您在其中一个调用中传递副本，以便将该路径放在不同的内存区域中，以便可以独立计算在当前点上分开的两条路径。

Answer 2

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

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

Recursion to print all paths in a matrix

java

algorithm

recursion