Print all possible paths from top left to bottom right of a mXn matrix

The problem, simply

You get a grid of numbers with m rows and n columns. Start in the top left cell and finish in the bottom right cell. Each step goes one cell right or one cell down.

Print every path, as the list of numbers you walk over.

A story to remember it

Picture it

Examples

Way 1: the simple way

Every path has exactly m - 1 downs and n - 1 rights, so m + n - 2 steps in total. Write down every string of R and D of that length, and keep only those with the right number of D's.

1. Count from 0 to 2^(m + n - 2) - 1. Read each number's bits as moves: 1 means down, 0 means right.
2. Skip the numbers that do not have exactly m - 1 ones.
3. For the rest, walk the moves from the top left and collect the cells.

import java.util.*;

class Solution {
    public List<List<Integer>> allPaths(int[][] grid) {
        int m = grid.length, n = grid[0].length, steps = m + n - 2;
        List<List<Integer>> result = new ArrayList<>();
        for (int mask = 0; mask < (1 << steps); mask++) {
            if (Integer.bitCount(mask) != m - 1) continue;   // must go down exactly m - 1 times
            List<Integer> path = new ArrayList<>();
            int r = 0, c = 0;
            path.add(grid[0][0]);
            for (int s = steps - 1; s >= 0; s--) {           // first move is the highest bit
                if ((mask >> s & 1) == 1) r++; else c++;
                path.add(grid[r][c]);
            }
            result.add(path);
        }
        return result;
    }
}

How long it takes: we look at all 2^(m+n-2) move strings and walk each one in O(m + n), so O(2^(m+n) * (m+n)). Most strings are thrown away. Extra room: one path, O(m + n), not counting the answers.

Way 2: the clever way

Only ever make moves that stay inside the grid. Then every walk that reaches the corner is a real answer, and nothing is thrown away.

1. Add the current cell to the path.
2. If it is the bottom right cell, save a copy of the path.
3. Otherwise, if there is a column to the right, go right. If there is a row below, go down.
4. Remove the current cell from the path before returning. This is the step back.

import java.util.*;

class Solution {
    public List<List<Integer>> allPaths(int[][] grid) {
        List<List<Integer>> result = new ArrayList<>();
        walk(grid, 0, 0, new ArrayList<>(), result);
        return result;
    }

    private void walk(int[][] grid, int r, int c, List<Integer> path, List<List<Integer>> result) {
        int m = grid.length, n = grid[0].length;
        path.add(grid[r][c]);
        if (r == m - 1 && c == n - 1) {
            result.add(new ArrayList<>(path));    // reached the corner
        } else {
            if (c + 1 < n) walk(grid, r, c + 1, path, result);   // right
            if (r + 1 < m) walk(grid, r + 1, c, path, result);   // down
        }
        path.remove(path.size() - 1);             // step back
    }
}

How long it takes: the number of paths is C(m+n-2, m-1), the ways to choose which steps are downs, and each path has m + n - 1 cells to copy. So O(C(m+n-2, m-1) * (m+n)). That is exactly the size of the output, so no method can be faster. Extra room: the path and the call stack, O(m + n).

Watch out for

• Forgetting to remove the cell when stepping back. Paths then grow forever and contain cells from other paths.
• Checking r < m before moving down instead of r + 1 < m. You walk off the grid.
• The number of paths explodes. A 10 by 10 grid has 48620 paths and a 16 by 16 grid has over 155 million. Ask about the size before printing.

What interviewers ask next

• Only count the paths. Use the formula C(m+n-2, m-1), or a table where each cell adds the count from above and the count from the left, O(m * n).
• Some cells are blocked. Skip moves into blocked cells. For counting, set the table to 0 on blocked cells.
• Find the path with the biggest sum. Use a table: each cell keeps its value plus the bigger of the best from above and from the left. No need to list every path.
• What if you may also go up and left? Then you can walk in circles, so you must mark cells on the current path and unmark them on the way back. That is the rat in a maze problem.

Remember this

Grown-up words: the grid is a matrix, the walks are paths in a grid graph, removing the cell on return is backtracking, and the number of paths is a binomial coefficient.