检查数组中是否有一个路径，其和在java中是递归求和

Question

我正在尝试编写下一个程序：

仅包含正整数的二维方形数组。每个单元格只能在路径上出现一次，编写一个递归布尔静态方法，该方法接受一个包含数字（大于零）和任何正和的二维mat数组作为参数，该方法作为与mat大小相同的二维数组的参数给出，该方法应检查数组中是否有一个和为和的路径。否则，将返回false值，并使用路径标记路径和和：最初，当路径数组作为参数传递时，其所有单元格在方法末尾包含和，如果mat数组和中有路径，则路径数组将在参与路径的单元格中包含1，在所有其他单元格中包含0。如果mat数组中没有此类路径，则路径数组应包含值0。如果有多条路径，则数组路径将包含其中一条路径。例如，给定阵列mat如下所示：

和4，则该方法返回true，路径数组可以是以下三个数组之一：

我试过：

public static boolean findSum(int i, int j, int mat[][], int sum, int path[][]){
    if(sum == 0) {
        return true;
    }else if(sum < 0) {
        return false;
    }else if (i < mat.length - 1 && findSum(i + 1, j, mat, sum - mat[i][j], path)) {
            path[i][j] = 1;
            return true;
    }else if (i < mat.length - 1 && findSum(i + 1, j, mat, sum, path))
            return true;
    else if (j < mat.length - 1 && findSum(i, j + 1, mat, sum - mat[i][j], path)) {
            path[i][j] = 1;
            return true;
    }else if (j < mat.length - 1 && findSum(i, j + 1, mat, sum, path))
            return true;
    return false;
}



public static boolean findSum (int mat[][], int sum, int path[][]){
    if(findSum(0,0, mat, sum, path)) {
        System.out.println(Arrays.deepToString(path));
        return true;
    }else {
        return false;
    }
}

我得到了：

1 | 0 | 0 | 0
1 | 0 | 0 | 0
1 | 0 | 0 | 0
0 | 0 | 0 | 0

问题是有两条路径的路径太长

Answer 1

假设您的算法在其他方面是正确的，我相信您传递的2D路径数组始终引用相同的数组。因此，当一个元素被设置为1时，数组的后续用法将始终将该元素也设置为1。解决此问题的最简单方法是执行以下操作（未检查语法）

    int[][] tempPath= new int[path.length()][path[0].size()];

    tempPath= path;