Find "path" in 2D array where path cells sum equals to "sum"

Question

Given 2D array of positive integers. A "path" is a collection of adjacent cells. Two cells are adjacent only from right/left/top/bottom (no diagonal).

The task is to write a function that receives a 2D array mat, an integer sum and a 2D array path (with same size as mat-empty array all zeros).

The function should check if path exist where the sum of cells equal to sum, should return true if exist and false otherwise.

The array path will mark the path (if exist with 1).

For example if mat is:

and sum=4

then path can be one of these three:

My code:

public static void main(String[] args) 
{
    int[][] mat={{2,41,3,14},
                 {2,1,24,7},
                 {2,15,10,54},
                 {63,22,2,4}};

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

public static boolean findSum (int mat[][], int sum, int path[][],int i,int j)
{
    if(sum==0)                      
        return true;

    if(i==mat[0].length||j==mat[1].length)
        return false;       
    boolean result=findSum(mat,sum-mat[i][j],path,i,j+1)||findSum(mat,sum-mat[i][j],path,i+1,j);

    if(result)
        path[i][j]=1;
    return result;

}
private static void print(int[][] arr)
{
    for(int i=0;i<arr[0].length;i++)
    {
        for(int j=0;j<arr[0].length;j++)
        {
            System.out.print(arr[i][j]+" ");
        }
        System.out.println();
    }
}

My code works fine only if the path starts at (0,0) but does't work for other pathes, for example it doesn't work(path array is all zero) for sum=16 even that there is such path.

Note:

• The function must be recursive- no loops at all.
• Global variables are not allowed (printing the array is not part of the question- only for test therefore there is a loop)

Answer 1

Nice question... Here is the answer. It was a fun code challenge ;)

public static void main(String[] args) 
{
    int[][] mat={{2,41,3,14},
                 {2,1,24,7},
                 {2,15,10,54},
                 {63,22,2,4}};

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

    if ( findSum(mat,22,path) ) print(path);
    else System.out.println("No path found");
}
public static boolean findSum (int mat[][], int sum, int path[][])
{
    return startPath(mat, sum, path, -1, 0);
}

// Recursively check every possible starting point
public static boolean startPath(int mat[][], int sum, int path[][], int y, int x)
{
    // Iterate y, goto next column if necessary
    if (++y == mat.length) {
        y = 0;
        ++x;
    }

    if (x == mat[0].length) // Bounds check
        return false;

    if (findSum(mat, sum, path, y, x)) // We've found a successful start point!
    {
        System.out.println("A successful path starts at " + x + ", " + y);
        return true;
    }

    return startPath(mat, sum, path, y, x); // We'll have to keep looking
}

public static boolean findSum (int mat[][], int sum, int path[][], int i, int j)
{
    if(i==mat[0].length || j==mat[1].length || i<0 || j<0) // Bounds check
        return false;

    if (path[i][j] == 1) // Backtracking check
        return false;

    sum -= mat[i][j]; // Decrement sum

    if (sum >= 0) { // More to go? look around
        path[i][j] = 1;

        if (sum == 0) return true; // We made it!

         // If any path finds the end, don't try other paths
        boolean result = findSum(mat, sum, path, i+1, j);
        if (result) return true;
        result = findSum(mat, sum, path, i, j+1);
        if (result) return true;
        result = findSum(mat, sum, path, i-1, j);
        if (result) return true;
        result = findSum(mat, sum, path, i, j-1);

         // There was no successful paths, this is a dead end
        if (!result) path[i][j] = 0;
        return result;
    } else { // We're negative, overshot it
        return false;
    }
}

private static void print(int[][] arr)
{
    for(int i=0;i<arr[0].length;i++)
    {
        for(int j=0;j<arr[0].length;j++)
        {
            System.out.print(arr[i][j]+" ");
        }
        System.out.println();
    }
}

By the way when checking multidimensional array dimensions you are meaning to do arr.length and arr[0].length but instead you are doing arr[0].length and arr[1].length which would get the same dimension twice and cause an error if the array was not a square.

I've also allowed moving in any direction, by using the intended path to prevent re-checking the same node again. This could probably be a boolean array. Sorry if my x/y recursion is rough looking... I really prefer loops or .forEach or => or .map for that...

The -1, 0 can be cleaned up perhaps with optional parameters and not iterating on the first pass.

Let me know if there are any errors or edge cases you may find.