给定2d整数数组，找到递归求和到给定数字的路径

Question

给定一个2d数组，我需要返回一个具有路径的矩阵，该路径递归地求和到给定的数字。

路径矩阵应为零，但总计为给定数字的路径除外，该路径将标记为1。

路径只能在

我尝试过所有的可能性，首先检查我是否已经去过下一个街区。

问题是在一些迭代之后，它会停止，并且不会返回并再次将块清除为0。

private static boolean paintPath(int[][] mat, int sum, int[][] path , int i, int j){

        if(sum<0)
            return false;

        path[i][j] = 1;

        if(sum == 0)
            return true;
        printMat(path);
        System.out.println();

        if(withinBoundaries(mat,i+1,j) && path[i+1][j] != 1)
            if(paintPath(mat,sum - mat[i][j],path,i+1,j))
                return true;

        if(withinBoundaries(mat,i,j+1) && path[i][j+1] != 1)
            if(paintPath(mat,sum - mat[i][j],path,i,j+1))
                return true;

        if(withinBoundaries(mat,i-1,j) && path[i-1][j] != 1)
            if(paintPath(mat,sum - mat[i][j],path,i-1,j))
                return true;
        if(withinBoundaries(mat,i,j-1) && path[i][j-1] != 1)
            if(paintPath(mat,sum - mat[i][j],path,i,j-1))
                 return true;

        path[i][j] = 0;
        return false;

    }

给定

int[][] mat1 = {
                {1,1,1,1},
                {5,100,100,1},
                {100,100,100,1},
                {1,1,1,1}
        };


 int[][] path = {
                {0,0,0,0},
                {0,0,0,0},
                {0,0,0,0},
                {0,0,0,0}
        };

在通话中

paintPath(mat1, 5, path, 0, 0);

我以为算法会回来

        {0,0,0,0},
        {1,0,0,0},
        {0,0,0,0},
        {0,0,0,0}

我得到

1   1   1   1   
0   0   1   1   
0   0   0   0   
0   0   0   0

相反

调用paintPath（mat1400，path，0，0）；我想

        {0,0,0,0},
        {0,1,1,0},
        {0,1,1,0},
        {0,0,0,0}

或

        {0,0,0,0},
        {0,0,1,0},
        {1,1,1,0},
        {0,0,0,0}

问题是，我的算法从（0,0）开始，然后从那里寻找路径，我需要它从任何起点找到任何路径（没有循环）

编辑：作业中引用的问题：“我们将数组中的路径定义为相邻单元格的集合。相邻的cekks可以从左、右、上、下相邻，但不能对角线相邻。每个单元格只能访问一次路径。编写一个递归方法，它接受一个包含大于0的整数、一个整数和正数的2d数组路径和一个与mat相同大小的2d数组路径。

该方法需要检查数组中是否存在其值之和等于sum的路径。如果有这样的路径，它应该返回true、false或otherwize。

数组路径用于标记其求和等于求和的路径。

路径单元格中的位置为1，其他单元格中的位置为0。

该方法必须是不带循环的RECCURSITIVE！因此，正如您将编写的任何其他方法一样。

可以使用重载。

您不能更换垫子。

Answer 1

更改此

path[i][j] = 1;

if(sum == 0)
  return true;
printMat(path);
System.out.println();

对此：

if(sum == 0){
  printMat(path);
  System.out.println();
  return true;
}

path[i][j] = 1;

请注意，您将获得输出，

{0,0,0,0},
{1,0,0,0},
{0,0,0,0},
{0,0,0,0}

如果您将起始呼叫更改为

paintPath(mat1, 5, path, 1, 0);