Return all paths from top-left to bottom-right in a grid

You're whiteboarding at a Microsoft interview and the interviewer slides a grid of letters across the table. "Imagine you're navigating through this board from the top-left corner to the bottom-right," they say. "You can only move down or right. I want you to return every possible path as a string of the letters you encounter along the way." This problem sits at the intersection of grid traversal, depth-first search, and backtracking, and it shows up regularly at companies like Microsoft and LinkedIn.

TL;DR

Use DFS with backtracking to explore every path from the top-left cell to the bottom-right cell, moving only down or right. Maintain a list of characters seen so far, and when you reach the destination, join them into a string and add it to a result set. After exploring both directions from a cell, remove the last character to restore state for the next branch. Time complexity is O(2^(m+n)) since you enumerate all possible paths, and space complexity is O(m + n) for the recursion depth.

Why This Problem Matters

This problem forces you to think about exhaustive search versus optimization. Many grid problems can be solved with dynamic programming, but when the interviewer asks you to return the actual paths rather than just a count, DP falls short. You need to explore every route, which means DFS with backtracking. Nail this pattern, and you'll be prepared for a whole family of grid and combinatorial problems.

Understanding the Problem

Given a 2D board of characters, find all paths from the top-left cell (0,0) to the bottom-right cell (m-1, n-1). You can only move downwards or rightwards, one cell at a time. Return all paths as a set of strings, where each string contains the characters encountered in order.

Let's start with a small 2x2 board:

From cell A, we have two choices: go right to B, or go down to C. Each choice leads to a different path ending at D.

Path 1: A, B, D (right, then down)

Path 2: A, C, D (down, then right)

So returnPaths([['A','B'],['C','D']]) returns {"ABD", "ACD"}.

Edge Cases to Consider

1. Single cell [['A']]: One path containing just "A"
2. Empty inner array [[]]: No valid path, return an empty set
3. Single row [['A','B','C']]: Only one path, "ABC"
4. Single column [['A'],['B'],['C']]: Only one path, "ABCD" going straight down
5. Larger grids: The number of paths grows combinatorially

Solution Approach

Since we need every path (not just a count), we need to explore all possibilities. DFS with backtracking is the right tool. Here is the thinking:

1. Start at (0,0) and add its character to our running list.
2. If we've reached the bottom-right corner, join the list into a string and record it.
3. Recursively explore moving down and then moving right.
4. After both recursive calls return, remove the last character (backtrack) so the parent call can try its next direction.

The Recursion Tree

For the 2x2 board, the DFS exploration looks like this:

Each leaf either reaches the destination (producing a valid path) or goes out of bounds (pruned). The two highlighted leaves at dfs(1,1) are where we record "ACD" and "ABD".

Backtracking in Action

The key mechanism is how charsSoFar changes as the recursion unfolds. Watch how the list grows and shrinks:

After recording "ACD", the algorithm backtracks by removing characters until it can explore the right branch from (0,0), eventually finding "ABD".

Implementation

Prefer a different language? Jump to solutions in other languages.

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Set;
import java.util.stream.Collectors;

public class Solution {
  public Set<String> returnPaths(char[][] board) {
    Set<String> paths = new HashSet<>();
    LinkedList<Character> charsSoFar = new LinkedList<>();
    dfs(board, paths, 0, 0, charsSoFar);
    return paths;
  }

  private void dfs(
    char[][] board,
    Set<String> paths,
    int r,
    int c,
    LinkedList<Character> charsSoFar
  ) {
    // Out of bounds: stop exploring this direction
    if (r == board.length || c == board[0].length) return;

    // Add current cell's character to the path
    charsSoFar.add(board[r][c]);

    // Reached the bottom-right corner: record the path
    if (r == board.length - 1 && c == board[0].length - 1) {
      paths.add(
        charsSoFar.stream()
          .map(String::valueOf)
          .collect(Collectors.joining())
      );
    }

    // Explore down and right
    dfs(board, paths, r + 1, c, charsSoFar);
    dfs(board, paths, r, c + 1, charsSoFar);

    // Backtrack: remove the character we added
    charsSoFar.removeLast();
  }
}

Let's trace through a slightly larger example to solidify understanding. For a 3x4 board:

With a 3-row, 4-column board, the algorithm produces 10 distinct paths. Every path is exactly 6 characters long (3 + 4 - 1 = 6 cells visited), since each path takes exactly 2 down-moves and 3 right-moves in some interleaved order.

Why the Implementation Works

A few details worth calling out:

• Bounds checking comes first. Before accessing board[r][c], we check whether r or c has gone past the edge. This prevents ArrayIndexOutOfBoundsException without needing separate checks for each direction.
• We add to the path before checking for the destination. The bottom-right cell is part of the path, so we add its character before testing whether we've arrived. If we checked first, the last character would be missing.
• Backtracking happens unconditionally. Whether we found a complete path or not, we always remove the last character before returning. This guarantees the parent call gets a clean state.

Complexity Analysis

Time Complexity: O(2^(m+n))

At each cell along the path, the algorithm branches into at most two directions. A complete path from (0,0) to (m-1, n-1) contains exactly (m + n - 2) steps. The total number of unique paths equals C(m+n-2, m-1), the binomial coefficient for choosing which steps go down. In the worst case, this is exponential in (m + n). Each path also requires O(m + n) work to join characters into a string.

Space Complexity: O(m + n)

The recursion depth is at most (m + n - 1), since each recursive call moves either down or right. The charsSoFar list holds at most (m + n - 1) characters. The output set holding all path strings uses additional space proportional to the number of paths times the path length, but that's typically considered output space rather than auxiliary space.

How This Compares to Counting Paths

If you only need the count, dynamic programming solves it in O(m * n) time and O(n) space. But DP cannot reconstruct the actual paths efficiently. When the interviewer asks for the paths themselves, exhaustive DFS is the appropriate approach.

Common Pitfalls

1. Forgetting to backtrack. If you don't remove the last character after the recursive calls, characters from the left subtree pollute the right subtree's path. Every path after the first will be wrong.

2. Checking bounds after accessing the cell. Accessing board[r][c] when r or c is out of bounds throws an exception. Always check bounds before touching the array.

3. Adding the character after the destination check. If you test for the bottom-right corner before adding the cell's character, your paths will be missing the final letter.

4. Using a mutable string instead of a list. While a StringBuilder works, character-by-character removal from the end of a StringBuilder is error-prone. A LinkedList<Character> with removeLast() makes the backtracking step explicit and hard to get wrong.

Interview Tips

When you encounter this problem in an interview:

1. Clarify the movement rules. "Can I only move down and right?" This confirms there's no diagonal or upward movement, which keeps the path count manageable.

2. Ask about the return type. A Set of strings is natural, but some interviewers might want a List. The algorithm is the same either way.

3. Draw the small example. Sketch the 2x2 grid, trace both paths, and show the backtracking step. This demonstrates understanding before you write code.

4. Mention the DP alternative for counting. Even though it doesn't solve this problem directly, noting that "if we only needed the count, we could use DP in O(m*n)" shows depth of knowledge.

5. Discuss the exponential growth. For large grids, the number of paths grows combinatorially. Mention that this is inherent to the problem, not a flaw in the algorithm. You cannot enumerate exponentially many paths in polynomial time.

Solutions in Other Languages

Python

class Solution:
    def return_paths(self, board):
        paths = set()
        chars_so_far = []
        self.dfs(board, paths, 0, 0, chars_so_far)
        return paths

    def dfs(self, board, paths, r, c, chars_so_far):
        if r == len(board) or c == len(board[0]):
            return
        chars_so_far.append(board[r][c])
        if r == len(board) - 1 and c == len(board[0]) - 1:
            paths.add("".join(chars_so_far))
        self.dfs(board, paths, r + 1, c, chars_so_far)
        self.dfs(board, paths, r, c + 1, chars_so_far)
        chars_so_far.pop()

JavaScript

class Solution {
  returnPaths(board) {
    const paths = new Set();
    const charsSoFar = [];
    this.dfs(board, paths, 0, 0, charsSoFar);
    return paths;
  }

  dfs(board, paths, r, c, charsSoFar) {
    if (r === board.length || c === board[0].length) return;
    charsSoFar.push(board[r][c]);
    if (r === board.length - 1 && c === board[0].length - 1) {
      paths.add(charsSoFar.join(""));
    }
    this.dfs(board, paths, r + 1, c, charsSoFar);
    this.dfs(board, paths, r, c + 1, charsSoFar);
    charsSoFar.pop();
  }
}

TypeScript

class Solution {
  returnPaths(board: string[][]): Set<string> {
    const paths = new Set<string>();
    const charsSoFar: string[] = [];
    this.dfs(board, paths, 0, 0, charsSoFar);
    return paths;
  }

  dfs(
    board: string[][],
    paths: Set<string>,
    r: number,
    c: number,
    charsSoFar: string[]
  ): void {
    if (r === board.length || c === board[0].length) return;
    charsSoFar.push(board[r][c]);
    if (r === board.length - 1 && c === board[0].length - 1) {
      paths.add(charsSoFar.join(""));
    }
    this.dfs(board, paths, r + 1, c, charsSoFar);
    this.dfs(board, paths, r, c + 1, charsSoFar);
    charsSoFar.pop();
  }
}

C++

#include <unordered_set>
#include <vector>
#include <string>

class Solution {
public:
  std::unordered_set<std::string> returnPaths(
    const std::vector<std::vector<char>>& board
  ) {
    std::unordered_set<std::string> paths;
    std::string charsSoFar;
    dfs(board, paths, 0, 0, charsSoFar);
    return paths;
  }

private:
  void dfs(
    const std::vector<std::vector<char>>& board,
    std::unordered_set<std::string>& paths,
    int r, int c,
    std::string& charsSoFar
  ) {
    if (r == board.size() || c == board[0].size()) return;
    charsSoFar.push_back(board[r][c]);
    if (r == board.size() - 1 && c == board[0].size() - 1) {
      paths.insert(charsSoFar);
    }
    dfs(board, paths, r + 1, c, charsSoFar);
    dfs(board, paths, r, c + 1, charsSoFar);
    charsSoFar.pop_back();
  }
};

Go

func ReturnPaths(board [][]rune) map[string]bool {
    paths := make(map[string]bool)
    charsSoFar := []rune{}
    dfs(board, paths, 0, 0, &charsSoFar)
    return paths
}

func dfs(board [][]rune, paths map[string]bool, r int, c int, charsSoFar *[]rune) {
    if r >= len(board) || c >= len(board[0]) {
        return
    }
    *charsSoFar = append(*charsSoFar, board[r][c])
    if r == len(board)-1 && c == len(board[0])-1 {
        paths[string(*charsSoFar)] = true
    }
    dfs(board, paths, r+1, c, charsSoFar)
    dfs(board, paths, r, c+1, charsSoFar)
    *charsSoFar = (*charsSoFar)[:len(*charsSoFar)-1]
}

Scala

import scala.collection.mutable

class Solution {
  def returnPaths(board: Array[Array[Char]]): Set[String] = {
    val paths = mutable.Set[String]()
    val charsSoFar = mutable.ArrayBuffer[Char]()
    dfs(board, paths, 0, 0, charsSoFar)
    paths.toSet
  }

  private def dfs(
    board: Array[Array[Char]],
    paths: mutable.Set[String],
    r: Int, c: Int,
    charsSoFar: mutable.ArrayBuffer[Char]
  ): Unit = {
    if (r == board.length || c == board(0).length) return
    charsSoFar.append(board(r)(c))
    if (r == board.length - 1 && c == board(0).length - 1)
      paths.add(charsSoFar.mkString(""))
    dfs(board, paths, r + 1, c, charsSoFar)
    dfs(board, paths, r, c + 1, charsSoFar)
    charsSoFar.dropRightInPlace(1)
  }
}

Kotlin

import java.util.HashSet
import java.util.LinkedList

class Solution {
  fun returnPaths(board: Array<CharArray>): Set<String> {
    val paths = HashSet<String>()
    val charsSoFar = LinkedList<Char>()
    dfs(board, paths, 0, 0, charsSoFar)
    return paths
  }

  private fun dfs(
    board: Array<CharArray>,
    paths: MutableSet<String>,
    r: Int, c: Int,
    charsSoFar: LinkedList<Char>
  ) {
    if (r == board.size || c == board[0].size) return
    charsSoFar.add(board[r][c])
    if (r == board.size - 1 && c == board[0].size - 1) {
      paths.add(charsSoFar.joinToString(""))
    }
    dfs(board, paths, r + 1, c, charsSoFar)
    dfs(board, paths, r, c + 1, charsSoFar)
    charsSoFar.removeLast()
  }
}

Swift

import Foundation

class Solution {
    func returnPaths(_ board: [[Character]]) -> Set<String> {
        var paths = Set<String>()
        var charsSoFar = [Character]()
        dfs(board, &paths, 0, 0, &charsSoFar)
        return paths
    }

    private func dfs(
        _ board: [[Character]],
        _ paths: inout Set<String>,
        _ r: Int, _ c: Int,
        _ charsSoFar: inout [Character]
    ) {
        if r == board.count || c == board[0].count { return }
        charsSoFar.append(board[r][c])
        if r == board.count - 1 && c == board[0].count - 1 {
            paths.insert(String(charsSoFar))
        }
        dfs(board, &paths, r + 1, c, &charsSoFar)
        dfs(board, &paths, r, c + 1, &charsSoFar)
        charsSoFar.removeLast()
    }
}

Ruby

require 'set'

class Solution
  def return_paths(board)
    paths = Set.new
    chars_so_far = []
    dfs(board, paths, 0, 0, chars_so_far)
    paths
  end

  def dfs(board, paths, r, c, chars_so_far)
    return if r == board.length || c == board[0].length
    chars_so_far << board[r][c]
    paths.add(chars_so_far.join) if r == board.length - 1 && c == board[0].length - 1
    dfs(board, paths, r + 1, c, chars_so_far)
    dfs(board, paths, r, c + 1, chars_so_far)
    chars_so_far.pop
  end
end

Rust

use std::collections::HashSet;

impl Solution {
    pub fn return_paths(&self, board: Vec<Vec<char>>) -> HashSet<String> {
        let mut paths = HashSet::new();
        let mut chars_so_far: Vec<char> = Vec::new();
        Self::dfs(&board, &mut paths, 0, 0, &mut chars_so_far);
        paths
    }

    fn dfs(
        board: &[Vec<char>],
        paths: &mut HashSet<String>,
        r: usize, c: usize,
        chars_so_far: &mut Vec<char>,
    ) {
        if r == board.len() || board.is_empty() || c == board[0].len() {
            return;
        }
        chars_so_far.push(board[r][c]);
        if r == board.len() - 1 && c == board[0].len() - 1 {
            paths.insert(chars_so_far.iter().collect());
        }
        Self::dfs(board, paths, r + 1, c, chars_so_far);
        Self::dfs(board, paths, r, c + 1, chars_so_far);
        chars_so_far.pop();
    }
}

C#

public class Solution {
    public HashSet<string> ReturnPaths(char[][] board) {
        var paths = new HashSet<string>();
        var charsSoFar = new List<char>();
        Dfs(board, paths, 0, 0, charsSoFar);
        return paths;
    }

    private void Dfs(
        char[][] board,
        HashSet<string> paths,
        int r, int c,
        List<char> charsSoFar
    ) {
        if (r == board.Length || c == board[0].Length) return;
        charsSoFar.Add(board[r][c]);
        if (r == board.Length - 1 && c == board[0].Length - 1) {
            paths.Add(new string(charsSoFar.ToArray()));
        }
        Dfs(board, paths, r + 1, c, charsSoFar);
        Dfs(board, paths, r, c + 1, charsSoFar);
        charsSoFar.RemoveAt(charsSoFar.Count - 1);
    }
}

Dart

class Solution {
  Set<String> returnPaths(List<List<String>> board) {
    Set<String> paths = {};
    List<String> charsSoFar = [];
    _dfs(board, paths, 0, 0, charsSoFar);
    return paths;
  }

  void _dfs(
    List<List<String>> board,
    Set<String> paths,
    int r, int c,
    List<String> charsSoFar,
  ) {
    if (r == board.length || c == board[0].length) return;
    charsSoFar.add(board[r][c]);
    if (r == board.length - 1 && c == board[0].length - 1) {
      paths.add(charsSoFar.join());
    }
    _dfs(board, paths, r + 1, c, charsSoFar);
    _dfs(board, paths, r, c + 1, charsSoFar);
    charsSoFar.removeLast();
  }
}

PHP

class Solution {
    public function returnPaths(array $board): array {
        $paths = [];
        $charsSoFar = [];
        $this->dfs($board, $paths, 0, 0, $charsSoFar);
        return $paths;
    }

    private function dfs(
        array $board,
        array &$paths,
        int $r, int $c,
        array &$charsSoFar
    ): void {
        if ($r === count($board) || $c === count($board[0])) return;
        $charsSoFar[] = $board[$r][$c];
        if ($r === count($board) - 1 && $c === count($board[0]) - 1) {
            $paths[] = implode('', $charsSoFar);
        }
        $this->dfs($board, $paths, $r + 1, $c, $charsSoFar);
        $this->dfs($board, $paths, $r, $c + 1, $charsSoFar);
        array_pop($charsSoFar);
    }
}

Related Problems

Once you're comfortable with this problem, try these related challenges:

• Count Paths on a Board (problem 51) asks for just the count, solvable with DP in O(m*n)
• Number of Islands (problem 107) applies DFS to a grid in a different way
• Grid Word Hunt (problem 226) explores grids for specific patterns using DFS

These problems share the core skill of navigating 2D grids with recursion. Practicing them together builds strong pattern recognition for matrix-based DFS questions.

Ready to practice this problem interactively? This problem and thousands of others are available on Firecode, where over 50,000 engineers have prepared for technical interviews at top companies. Build your skills one problem at a time.