CODEWITHSUNDEEP
javarecursion
Omer Segal
Omer Segal

Reputation: 65

Given 2d array of integers, find a path that sum up to a given number recursively

Given a 2d array, I need to return a matrix with a path that sum up to a given number, recursively.

the path matrix should be zeros except for the path that sums up to the given number which will be marked with 1.

A path could only go left/right up/down in the

I have tried to go over all the possibilities, checking first if I already been to the next block.

the problem is that after some iterations it stops, and doesnt go back and clear the block to be 0 again.

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;

    }

given

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

with the call

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

I expected the algorithm to return

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

I get

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

Instead.

And from a call to paintPath(mat1, 400, path, 0, 0); I expect 

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

or 

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

The problem is that my algorithm start from (0,0) and look for a path from there, I need it to find any path from any start point (without a loop)

edit: The problem quoted from the assignment: "We define a path in an array as a collection of adjacent cells. adjacent cekks can be adjacent from left,right,up,down but not diagonal. each cell can accure in the path only once. write a recursive method, which accepts a 2d array mat which contains integers greater than 0, an integer sum poisitive number, and a 2d array path same size as mat.

the method is requierd to check if there is a path in the array that the sum of it values equals to sum. if there is such a path it should return true, false otherwize.

the array path is used to mark the path that it sum euquals to sum.

path will have 1's where in the path cells and 0s in the other cells.

The method must be reccursive without loops at all! so as any other method you will write.

you can use overloading.

you cannot change mat.

Upvotes: 3

Views: 562

Answers (1)

גלעד ברקן
גלעד ברקן

Reputation: 23955

Change this

path[i][j] = 1;

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

to this:

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

path[i][j] = 1;

Note that you would get the output,

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

if you changed the starting call to

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

Upvotes: 2

Related Questions