paths in a grid with recursive function

December 27, 2021

I have a grid of size NxN and I understand that this recursive function finds the number of paths from (0, 0) to (N – 1, N – 1) but is there a way I can change this function to print out the path instead of just how many there are?

public static int countPaths(int[][] grid, int r, int c) {
        if(r == grid.length - 1 || c == grid.length - 1) {
            return 1;
        }
        
        return countPaths(grid, r + 1, c) + countPaths(grid, r, c + 1);
    }

>Solution :

this recursive function finds the number of paths from (0, 0) to (N – 1, N – 1)

This is not exactly true, it will every path from (0, 0) to either the last row [(0, N - 1), (1, N - 1), ... (N - 2, N - 1)] or either last column [(N - 1, 0), (N - 1, 1), ..., (N - 1, N - 2)] of the grid. In fact, it will never reach (N - 1, N - 1). To visualize all of these paths, we can do the following:

public static int countPaths(int[][] grid, int r, int c, List<int[]> path) {
    if (r == grid.length - 1 || c == grid.length - 1) {
        path.forEach(p -> System.out.print(Arrays.toString(p)));
        System.out.println();
        return 1;
    }

    List<int[]> path1 = new ArrayList<>(path);
    path1.add(new int[]{r + 1, c});
    List<int[]> path2 = new ArrayList<>(path);
    path2.add(new int[]{r, c + 1});
    return countPaths(grid, r + 1, c, path1) + countPaths(grid, r, c + 1, path2);
}

Now we should call our method as such:

int[][] grid = new int[N][N];
System.out.println(countPaths(grid, 0, 0, new ArrayList<>(List.of(new int[]{0, 0}))));

For example, if N = 4, it will print out the following for the paths:

[0, 0][1, 0][2, 0][3, 0]
[0, 0][1, 0][2, 0][2, 1][3, 1]
[0, 0][1, 0][2, 0][2, 1][2, 2][3, 2]
[0, 0][1, 0][2, 0][2, 1][2, 2][2, 3]
[0, 0][1, 0][1, 1][2, 1][3, 1]
[0, 0][1, 0][1, 1][2, 1][2, 2][3, 2]
[0, 0][1, 0][1, 1][2, 1][2, 2][2, 3]
[0, 0][1, 0][1, 1][1, 2][2, 2][3, 2]
[0, 0][1, 0][1, 1][1, 2][2, 2][2, 3]
[0, 0][1, 0][1, 1][1, 2][1, 3]
[0, 0][0, 1][1, 1][2, 1][3, 1]
[0, 0][0, 1][1, 1][2, 1][2, 2][3, 2]
[0, 0][0, 1][1, 1][2, 1][2, 2][2, 3]
[0, 0][0, 1][1, 1][1, 2][2, 2][3, 2]
[0, 0][0, 1][1, 1][1, 2][2, 2][2, 3]
[0, 0][0, 1][1, 1][1, 2][1, 3]
[0, 0][0, 1][0, 2][1, 2][2, 2][3, 2]
[0, 0][0, 1][0, 2][1, 2][2, 2][2, 3]
[0, 0][0, 1][0, 2][1, 2][1, 3]
[0, 0][0, 1][0, 2][0, 3]