Checking for sum inside matrix and keep the path on second array recursively

Question

This question was on my end of semester test on Java:

Given a matrix of positive numbers (unsorted) m, an integer sum and another matrix p that filled with 0 all over. recursively check if there is a path inside m that the sum of it will be equal to sum.

the rules:

you can only travel to down , up , left or right in the array.

after you've found the path , the matrix p will be filled with 1's on the correct path.

there is only 1 path

all other cells on p should be 0 after the method has finished.

if there is no path to this sum you will leave p as you got him.

EXAMPLE:

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

in the beginning.

the matrix is:

        int [][] hill = {{3,8,7,1},
                         {5,15,2,4},
                         {12,14,-13,22},
                         {13,16,17,52}};

if you call the method on sum = 23 the method will return true , and p will be:

        int[][] p = {{1,0,0,0},
                     {1,1,0,0},
                     {0,0,0,0},
                     {0,0,0,0}};

THE METHOD MUST BE RECURSIVE

this question just made the test like hell...

Hope you can figure it out and maybe help me to understand it!! THANKS

my progress:

    public static boolean findSum(int[][] mat , int sum , int[][]path){
    return findSum(mat,sum,path,0,0);
}

private static boolean findSum(int[][] m, int sum, int[][] p, int i, int j) {
    if (i>=m.length || j>= m[i].length) return false;


    boolean op1 = finder(m,sum-m[i][j],p,i,j);
    boolean op2 = findSum(m,sum,p,i+1,j);
    boolean op3 = findSum(m,sum,p,i,j+1);

    if (op1) return true;
    else if (op2) return true;
    return op3;
}

private static boolean finder(int[][] m, int sum,int[][]p , int i, int j) {

    if (sum==0) {
        p[i][j]=1;
        return true;
    }
    p[i][j]=1;
    boolean op1=false,op2=false,op3=false,op4=false;
    if (i>0 && p[i-1][j]==0 && sum-m[i][j]>=0) op1 = finder(m, sum - m[i][j], p, i - 1, j);
    if (i<m.length-1 && p[i+1][j]==0&& sum-m[i][j]>=0) op2 = finder(m, sum - m[i][j], p, i + 1, j);
    if (j>0 && p[i][j-1]==0&& sum-m[i][j]>=0) op3 = finder(m, sum - m[i][j], p, i, j - 1);
    if (j<m[i].length-1 && p[i][j+1]==0&& sum-m[i][j]>=0) op4 = finder(m, sum - m[i][j], p, i, j + 1);
    else p[i][j]=0;
    return op1||op2||op3||op4;

}

Answer 1

so I managed to make it work :) with some help from my course instructor here is a full java solution!

public static boolean findSum(int[][] m ,int s, int[][]p){
    return findSum(m,s,p,0,0); //calling overloading
}

private static boolean findSum(int[][] m, int s, int[][] p, int i, int j) {
    if (i<0 || i>=m.length) return false; //stop condition
    if (finder(m,s,p,i,j)) return true; //first recursion
    if (j<m[0].length-1) //if the iterator is not on the end of the row 
        return  findSum(m,s,p,i,j+1); //recursive call 
    else //if i checked the whole row , the column will be increase.
        return findSum(m,s,p,i+1,0);//recursive call

}

private static boolean finder(int[][] m, int s, int[][] p, int i, int j) {
    if (s == 0) return true;
    if (i<0 || i>=m.length || j<0 || j>=m.length || s<0 || p[i][j] == 1) return false;

    p[i][j] =1;
    boolean u=false,d=false,r=false,l=false;
    if (i>0) u = finder(m,s-m[i][j],p,i-1,j);
    if (i<m.length-1) d = finder(m,s-m[i][j],p,i+1,j);
    if (j>0) l = finder(m,s-m[i][j],p,i,j-1);
    if (i<m.length-1) r = finder(m,s-m[i][j],p,i,j+1);
    if (u) return true;
    else if (d) return true;
    else if (r) return true;
    else if (l) return true;
    else {
        p[i][j] = 0;
        return false;
    }
}

Answer 2

I really enjoyed solving this problem. I have done it in python but you can easily extend it to Java. I have commented the code for your understanding. Let me know if there is anything you dont get or can be improved.

btw there are multiple paths for one sum in your example, and the code below finds all.

hill = [[3,8,7,1],[5,15,2,4],[12,14,-13,22],[13,16,17,52]]
p = [ [0 for x in range (4)] for y in range(4)]
num = 23

def checkPath(p, r, c): #Check boundaries
    res = []
    if r+1<len(p):
        res.append(p[r+1][c] == 0)
    if r-1>=0:
        res.append(p[r-1][c] == 0)
    if c+1<len(p[0]):
        res.append(p[r][c+1] == 0)
    if c-1>=0:
        res.append(p[r][c-1] == 0)
    return res


def pathF(tot, hill, p, r, c):
    p[r][c] = 1 #mark visited
    tot = tot + hill[r][c]    #update total

    if tot == num: #solution found
        print("Found", p)
    else:
        if any (checkPath(p,r,c)):
            if r+1<len(p) and p[r+1][c] == 0: #move right checking if it wasnt visited
                  pathF(tot,hill,p,r+1,c)
            if r-1>=0 and p[r-1][c] == 0:
                pathF(tot,hill,p,r-1,c)
            if c+1<len(p[0]) and p[r][c+1] == 0:
                pathF(tot,hill,p,r,c+1)
            if c-1>=0 and p[r][c-1] == 0:
                pathF(tot,hill,p,r,c-1)
    p[r][c]=0 #mark unvisited
    tot = tot - hill[r][c]     #set total to original       


for x in range(len(hill)): #iterate over every starting point possible
    for y in range(len(hill[0])):
        pathF(0,hill,p,x,y)

This is the output with num = 23

Found [[1, 0, 0, 0], [1, 0, 1, 0], [1, 1, 1, 0], [0, 0, 0, 0]]
Found [[1, 0, 0, 0], [1, 1, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
Found [[1, 1, 1, 1], [0, 0, 0, 1], [0, 0, 0, 0], [0, 0, 0, 0]]
Found [[0, 1, 0, 0], [0, 1, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
Found [[0, 1, 1, 1], [0, 0, 1, 1], [0, 1, 1, 0], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[1, 1, 1, 0], [1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 0, 1], [0, 1, 1, 1], [0, 1, 1, 0], [0, 0, 0, 0]]
Found [[0, 0, 0, 1], [0, 1, 1, 1], [0, 1, 1, 0], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 0], [1, 1, 1, 0], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[1, 1, 1, 0], [1, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
Found [[0, 0, 0, 0], [1, 1, 1, 0], [0, 1, 1, 0], [0, 0, 0, 0]]
Found [[0, 0, 0, 0], [1, 1, 1, 0], [0, 1, 1, 0], [0, 0, 0, 0]]
Found [[0, 0, 0, 1], [0, 1, 1, 1], [0, 1, 1, 0], [0, 0, 0, 0]]
Found [[0, 1, 0, 0], [0, 1, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
Found [[1, 0, 0, 0], [1, 1, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 0, 0], [1, 1, 1, 0], [0, 1, 1, 0], [0, 0, 0, 0]]
Found [[1, 0, 0, 0], [1, 0, 1, 0], [1, 1, 1, 0], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[1, 1, 1, 1], [0, 0, 0, 1], [0, 0, 0, 0], [0, 0, 0, 0]]
Found [[0, 0, 0, 0], [0, 0, 1, 1], [0, 1, 1, 0], [0, 1, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 0], [1, 1, 1, 0], [0, 0, 0, 0]]
Found [[0, 1, 1, 1], [0, 0, 1, 1], [0, 1, 1, 0], [0, 0, 0, 0]]
Found [[0, 0, 0, 0], [1, 1, 1, 0], [0, 1, 1, 0], [0, 0, 0, 0]]
Found [[0, 0, 0, 0], [0, 0, 0, 0], [0, 1, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 0, 1], [0, 1, 1, 1], [0, 1, 1, 0], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 0, 0], [0, 0, 0, 0], [0, 1, 1, 1], [0, 0, 0, 0]]
Found [[0, 0, 0, 0], [0, 0, 1, 1], [0, 1, 1, 0], [0, 1, 0, 0]]