Check whether there is a path in an array whose sum is sum by recursion in java

Question

I'm trying to write the next program:

A two-dimensional square array containing only positive integers. Each cell can appear on the path only once, write a recursive boolean static method that accepts as a parameter a two-dimensional mat array containing numbers (Which is greater than zero) and any positive sum sum, and the method is given as a parameter of a two-dimensional array of the same size as mat, which should check if there is a path in an array whose sum is sum. Otherwise the false value will be returned, and the path is used to mark the path sum sum: Initially, when the path array is passed as a parameter, all its cells contain the sum At the end of the method, if there is a path in a mat array sum sum, the path array will contain 1 in the cells participating in the path and 0 in all the other cells.If there is no such path in the mat array, the path array should contain the value 0 if there is more than one path One sum sum, the array path will contain one of the paths sum sum (arbitrarily). For example, given the array mat follows:

And the sum 4, the method returns true and the path array can be one of the following three arrays:

I tried:

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

And I got:

1 | 0 | 0 | 0
1 | 0 | 0 | 0
1 | 0 | 0 | 0
0 | 0 | 0 | 0

The problem is that I get too long a path with 2 paths

See [What is a debugger and how can it help me diagnose problems?](https://stackoverflow.com/q/25385173/5221149) and [How to debug small programs](https://ericlippert.com/2014/03/05/how-to-debug-small-programs/) — Andreas, Jun 02 '19 at 20:38

score 0 · Answer 1 · answered Jun 02 '19 at 20:43

Assuming your algorithm is otherwise correct, I believe the 2D path array you are passing around references the same array all the time. Therefore, when an element is set to 1 once, later usages of the array will always have that element as 1 also. The easiest way to fix this is to do something like (syntax not checked)

    int[][] tempPath= new int[path.length()][path[0].size()];

    tempPath= path;

Check whether there is a path in an array whose sum is sum by recursion in java

1 Answers1