Walk into cells, mark them visited so you never loop, and un-mark on the way out so other paths can reuse them.
“Count/find all paths on a grid” / “path touching specific rules” → DFS + unmark
Pattern 1: Unique Paths (obstacle grid)
Count every route from top-left to bottom-right:
public int uniquePaths(int[][] g) {
return walk(g, 0, 0);
}
int walk(int[][] g, int r, int c) {
if (r >= g.length || c >= g[0].length || g[r][c] == 1)
return 0;
if (r == g.length - 1 && c == g[0].length - 1)
return 1;
g[r][c] = 1; // mark
int paths = walk(g, r+1, c) + walk(g, r, c+1);
g[r][c] = 0; // BACKTRACK
return paths;
}def unique_paths(g):
m, n = len(g), len(g[0])
def walk(r, c):
if r >= m or c >= n or g[r][c] == 1:
return 0
if (r, c) == (m - 1, n - 1):
return 1
g[r][c] = 1 # mark
paths = walk(r + 1, c) + walk(r, c + 1)
g[r][c] = 0 # BACKTRACK
return paths
return walk(0, 0)int walk(vector<vector<int>>& g, int r, int c) {
int m = g.size(), n = g[0].size();
if (r >= m || c >= n || g[r][c] == 1) return 0;
if (r == m-1 && c == n-1) return 1;
g[r][c] = 1; // mark
int paths = walk(g, r+1, c) + walk(g, r, c+1);
g[r][c] = 0; // BACKTRACK
return paths;
}
int uniquePaths(vector<vector<int>>& g) {
return walk(g, 0, 0);
}function uniquePaths(g) {
const walk = (r, c) => {
if (r >= g.length || c >= g[0].length || g[r][c] === 1)
return 0;
if (r === g.length - 1 && c === g[0].length - 1)
return 1;
g[r][c] = 1; // mark
const paths = walk(r + 1, c) + walk(r, c + 1);
g[r][c] = 0; // BACKTRACK
return paths;
};
return walk(0, 0);
}Counting paths this way is exponential; add memoization on
(r,c)→ O(m·n) — that’s just DP then. Pure backtracking is for FINDING/ENUMERATING paths.
Pattern 2: Rat in a Maze (any valid path)
public List<int[]> findPath(int[][] maze) {
List<int[]> path = new ArrayList<>();
solve(maze, 0, 0, path);
return path;
}
boolean solve(int[][] m, int r, int c, List<int[]> path) {
int n = m.length;
if (r < 0 || c < 0 || r >= n || c >= n
|| m[r][c] == 0) return false;
path.add(new int[]{r, c});
if (r == n-1 && c == n-1) return true;
m[r][c] = 0; // mark as used
for (int[] d : new int[][]{{1,0},{0,1},{-1,0},{0,-1}})
if (solve(m, r+d[0], c+d[1], path)) return true;
m[r][c] = 1; // BACKTRACK
path.remove(path.size() - 1);
return false;
}def find_path(maze):
n, path = len(maze), []
def solve(r, c):
if not (0 <= r < n and 0 <= c < n) or maze[r][c] == 0:
return False
path.append((r, c))
if (r, c) == (n - 1, n - 1):
return True
maze[r][c] = 0 # mark
for dr, dc in ((1,0),(0,1),(-1,0),(0,-1)):
if solve(r + dr, c + dc):
return True
maze[r][c] = 1 # BACKTRACK
path.pop()
return False
return path if solve(0, 0) else []bool solve(vector<vector<int>>& m, int r, int c,
vector<pair<int,int>>& path) {
int n = m.size();
if (r < 0 || c < 0 || r >= n || c >= n || !m[r][c])
return false;
path.push_back({r, c});
if (r == n-1 && c == n-1) return true;
m[r][c] = 0; // mark
int dr[] = {1,0,-1,0}, dc[] = {0,1,0,-1};
for (int k = 0; k < 4; k++)
if (solve(m, r+dr[k], c+dc[k], path)) return true;
m[r][c] = 1; // BACKTRACK
path.pop_back();
return false;
}function findPath(maze) {
const n = maze.length,
path = [];
const solve = (r, c) => {
if (r < 0 || c < 0 || r >= n || c >= n || !maze[r][c])
return false;
path.push([r, c]);
if (r === n - 1 && c === n - 1) return true;
maze[r][c] = 0; // mark
for (const [dr, dc] of [[1,0],[0,1],[-1,0],[0,-1]])
if (solve(r + dr, c + dc)) return true;
maze[r][c] = 1; // BACKTRACK
path.pop();
return false;
};
return solve(0, 0) ? path : [];
}Pattern 3: Word Search (letters grid)
DFS dives down-right, hits the wall at (2,3), and the successful path threads through (3,2). Press ▶.
⚠️ Animation & Content Notice
The animation work is not fully finished — some animations may have slight errors.
If there is a major error in the content or if the animation or content is difficult to understand, please contact us at rayyancodingschool@gmail.com.
Rat in a Maze
Find a path from (0,0) to the goal in a grid where 1=open and 0=wall.
DFS marks a cell visited, then tries directions in order (down, right, up, left). Reaching the goal returns true up the call stack; a dead end unmarks the cell (backtrack) and the parent tries its next option. The unwinding of failed branches IS backtracking.
GRID VISUALIZER
Steps –
1
1
0
1
1
1
1
1
0
1
1
0
1
1
1
1
Press ▶ to animate, or step through manually.
Variables
keys: ← → space F
Pseudocode
1
solve(r, c):
2
if outside || wall || visited: return false
3
visit(r,c)
4
if (r,c) == goal: return true
5
for dir in [down, right, up, left]:
6
if solve(nr, nc): return true
7
unvisit(r,c) # BACKTRACK
8
return false
Same skeleton — mark cell, try 4 directions, unmark:
public boolean exist(char[][] b, String word) {
for (int r = 0; r < b.length; r++)
for (int c = 0; c < b[0].length; c++)
if (match(b, r, c, word, 0)) return true;
return false;
}
boolean match(char[][] b, int r, int c, String w, int i) {
if (i == w.length()) return true;
if (r < 0 || c < 0 || r >= b.length || c >= b[0].length
|| b[r][c] != w.charAt(i)) return false;
char saved = b[r][c];
b[r][c] = '#'; // mark
boolean ok = match(b,r+1,c,w,i+1) || match(b,r-1,c,w,i+1)
|| match(b,r,c+1,w,i+1) || match(b,r,c-1,w,i+1);
b[r][c] = saved; // BACKTRACK
return ok;
}def exist(board, word):
m, n = len(board), len(board[0])
def match(r, c, i):
if i == len(word): return True
if not (0 <= r < m and 0 <= c < n) \
or board[r][c] != word[i]:
return False
saved, board[r][c] = board[r][c], "#" # mark
ok = (match(r+1,c,i+1) or match(r-1,c,i+1) or
match(r,c+1,i+1) or match(r,c-1,i+1))
board[r][c] = saved # BACKTRACK
return ok
return any(match(r, c, 0)
for r in range(m) for c in range(n))bool match(vector<vector<char>>& b, int r, int c,
const string& w, int i) {
if (i == (int)w.size()) return true;
if (r < 0 || c < 0 || r >= (int)b.size()
|| c >= (int)b[0].size() || b[r][c] != w[i])
return false;
char saved = b[r][c];
b[r][c] = '#'; // mark
bool ok = match(b,r+1,c,w,i+1) || match(b,r-1,c,w,i+1)
|| match(b,r,c+1,w,i+1) || match(b,r,c-1,w,i+1);
b[r][c] = saved; // BACKTRACK
return ok;
}
bool exist(vector<vector<char>>& b, string word) {
for (int r = 0; r < (int)b.size(); r++)
for (int c = 0; c < (int)b[0].size(); c++)
if (match(b, r, c, word, 0)) return true;
return false;
}function exist(board, word) {
const m = board.length,
n = board[0].length;
const match = (r, c, i) => {
if (i === word.length) return true;
if (r < 0 || c < 0 || r >= m || c >= n ||
board[r][c] !== word[i]) return false;
const saved = board[r][c];
board[r][c] = "#"; // mark
const ok =
match(r + 1, c, i + 1) || match(r - 1, c, i + 1) ||
match(r, c + 1, i + 1) || match(r, c - 1, i + 1);
board[r][c] = saved; // BACKTRACK
return ok;
};
for (let r = 0; r < m; r++)
for (let c = 0; c < n; c++)
if (match(r, c, 0)) return true;
return false;
}Mark on entry, unmark on exit — forgetting the second half turns backtracking into BFS-wannabe garbage.
Common Mistakes
- Marking visited but never UNMARKING → kills valid overlapping paths.
- Checking bounds AFTER accessing the array (crash).
- Word search: reusing the same cell twice within one word (that’s what ’#’ marking prevents).
- Returning after first success in counting problems — you need ALL paths, no early exit.
Complexity
| Problem | Time | Space |
|---|---|---|
| Unique paths (pure) | O(2^(m+n)) | O(m+n) stack |
| Rat in maze | O(4^(m·n)) worst | O(m·n) |
| Word search | O(m·n·4^L) | O(L) |
Premium Content
Unlock Grid Backtracking and all premium lessons with a subscription.
All premium lessons
Ad-free experience
Priority support
From ₹199.99/year — See plans