java - java中通过递归检查数组中是否存在sum为sum的路径

Question

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

仅包含正整数的二维方阵。 每个单元格只能在路径上出现一次，编写一个递归 boolean 静态方法，该方法接受包含数字(大于零)和任何正和的二维 mat 数组作为参数，并将该方法作为参数给出与 mat 大小相同的二维数组，它应该检查数组中是否存在总和为 sum 的路径。否则将返回 false 值，path 用于标记路径总和 sum: 最初，当路径数组作为参数传递时，其所有单元格都包含 sum 在方法结束时，如果存在路径在 mat 数组 sum sum 中，路径数组将在参与路径的单元格中包含 1，在所有其他单元格中包含 0。如果 mat 数组中没有这样的路径，则路径数组应包含值 0(如果有)多个路径 一个 sum sum，数组路径将包含其中一个路径 sum sum(任意)。例如，给定数组垫如下:

和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;