Skip to content

Recursion and Backtracking Problems — Complete Interview Guide

DodaTech Updated 2026-06-23 6 min read

In this tutorial, you'll learn about Recursion and Backtracking Problems. We cover key concepts, practical examples, and best practices to help you understand and apply this topic effectively.

Recursion solves problems by breaking them into smaller instances of the same problem. Backtracking extends Recursion by exploring all candidates and abandoning partial solutions that cannot be completed.

Learning Path

flowchart LR
  A["Sorting & Searching"] --> B["Recursion & Backtracking
You are here"]
  B --> C["Heap, Stack & Queue"]
  C --> D["System Design Prep"]
  style B fill:#f90,color:#fff,stroke-width:2px

Subsets (Power Set)

Generate all subsets of a set. This is the simplest Backtracking problem and the foundation for all others.

def subsets(nums):
    result = []
    def backtrack(start, path):
        result.append(path[:])
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1, path)
            path.pop()
    backtrack(0, [])
    return result

print(subsets([1, 2, 3]))

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

import java.util.*;

public class Subsets {
    public static List<List<Integer>> subsets(int[] nums) {
        List<List<Integer>> result = new ArrayList<>();
        backtrack(nums, 0, new ArrayList<>(), result);
        return result;
    }

    private static void backtrack(int[] nums, int start, List<Integer> path, List<List<Integer>> result) {
        result.add(new ArrayList<>(path));
        for (int i = start; i < nums.length; i++) {
            path.add(nums[i]);
            backtrack(nums, i + 1, path, result);
            path.remove(path.size() - 1);
        }
    }

    public static void main(String[] args) {
        System.out.println(subsets(new int[]{1, 2, 3}));
    }
}

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

#include <vector>
#include <iostream>
using namespace std;

void backtrack(vector<int>& nums, int start, vector<int>& path, vector<vector<int>>& result) {
    result.push_back(path);
    for (int i = start; i < nums.size(); i++) {
        path.push_back(nums[i]);
        backtrack(nums, i + 1, path, result);
        path.pop_back();
    }
}

vector<vector<int>> subsets(vector<int>& nums) {
    vector<vector<int>> result;
    vector<int> path;
    backtrack(nums, 0, path, result);
    return result;
}

int main() {
    vector<int> nums = {1, 2, 3};
    auto res = subsets(nums);
    for (auto& subset : res) {
        cout << "[";
        for (int v : subset) cout << v << " ";
        cout << "] ";
    }
    return 0;
}

[] [1] [1 2] [1 2 3] [1 3] [2] [2 3] [3]

N-Queens

Place N queens on an NxN board so that no two queens attack each other. This is the classic Backtracking problem with constraint checking.

def solve_n_queens(n):
    col = set()
    pos_diag = set()  # r + c
    neg_diag = set()  # r - c
    board = [["."] * n for _ in range(n)]
    result = []

    def backtrack(r):
        if r == n:
            result.append(["".join(row) for row in board])
            return
        for c in range(n):
            if c in col or (r + c) in pos_diag or (r - c) in neg_diag:
                continue
            col.add(c)
            pos_diag.add(r + c)
            neg_diag.add(r - c)
            board[r][c] = "Q"
            backtrack(r + 1)
            col.remove(c)
            pos_diag.remove(r + c)
            neg_diag.remove(r - c)
            board[r][c] = "."

    backtrack(0)
    return result

solutions = solve_n_queens(4)
for sol in solutions:
    print("\n".join(sol))
    print()

.Q..
...Q
Q...
..Q.

..Q.
Q...
...Q
.Q..

Permutations

Generate all permutations of an array. Unlike subsets, order matters and all elements must be used.

def permute(nums):
    result = []
    def backtrack(path, remaining):
        if not remaining:
            result.append(path[:])
            return
        for i, num in enumerate(remaining):
            path.append(num)
            backtrack(path, remaining[:i] + remaining[i + 1:])
            path.pop()
    backtrack([], nums)
    return result

print(permute([1, 2, 3]))

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

Sudoku Solver

Fill a 9x9 Sudoku board by Backtracking through empty cells and trying valid numbers.

def solve_sudoku(board):
    def is_valid(r, c, num):
        for i in range(9):
            if board[r][i] == num:
                return False
            if board[i][c] == num:
                return False
            box_r, box_c = 3 * (r // 3) + i // 3, 3 * (c // 3) + i % 3
            if board[box_r][box_c] == num:
                return False
        return True

    def backtrack():
        for r in range(9):
            for c in range(9):
                if board[r][c] == ".":
                    for num in "123456789":
                        if is_valid(r, c, num):
                            board[r][c] = num
                            if backtrack():
                                return True
                            board[r][c] = "."
                    return False
        return True

    backtrack()

board = [
    ["5","3",".",".","7",".",".",".","."],
    ["6",".",".","1","9","5",".",".","."],
    [".","9","8",".",".",".",".","6","."],
    ["8",".",".",".","6",".",".",".","3"],
    ["4",".",".","8",".","3",".",".","1"],
    ["7",".",".",".","2",".",".",".","6"],
    [".","6",".",".",".",".","2","8","."],
    [".",".",".","4","1","9",".",".","5"],
    [".",".",".",".","8",".",".","7","9"]
]
solve_sudoku(board)
for row in board:
    print(row)

['5', '3', '4', '6', '7', '8', '9', '1', '2']
['6', '7', '2', '1', '9', '5', '3', '4', '8']
['1', '9', '8', '3', '4', '2', '5', '6', '7']
['8', '5', '9', '7', '6', '1', '4', '2', '3']
['4', '2', '6', '8', '5', '3', '7', '9', '1']
['7', '1', '3', '9', '2', '4', '8', '5', '6']
['9', '6', '1', '5', '3', '7', '2', '8', '4']
['2', '8', '7', '4', '1', '9', '6', '3', '5']
['3', '4', '5', '2', '8', '6', '1', '7', '9']

Common Mistakes

  1. Missing base case -- Every recursive function must have a termination condition. Forgetting it causes infinite Recursion and stack overflow.
  2. Not restoring state -- Backtracking requires undoing changes after Recursion returns. Always pop path entries or reset board cells.
  3. Deep copy vs reference -- Appending path instead of path[:] stores a reference that mutates after Backtracking. Always copy the current state.
  4. No pruning -- Without constraint checking, Backtracking explores all possibilities including invalid ones. Prune early with validity checks.
  5. Stack depth limits -- Python's default Recursion limit is 1000. For problems requiring deeper Recursion, use iterative approaches or increase the limit.
  6. Redundant computation -- Recalculating valid candidates on each call without Caching leads to exponential time. Precompute or use incremental validation.
  7. Wrong parameter passing -- Passing lists by reference in C++ without copying causes unintended mutation. Use const references for read-only data.

Practice Questions

1. Generate all combinations of k numbers from 1 to n.

Modify the subset pattern to stop when path length reaches k. Use pruning: if remaining numbers + current length < k, skip.

2. Letter combinations of a phone number (Leetcode 17).

Map digits to letters recursively. Build combinations by iterating over each digit's letters and recursing for the next digit.

3. Challenge: Word Search (Leetcode 79)

Given a 2D board and a word, find if the word exists. Use DFS with Backtracking, marking visited cells temporarily to avoid reuse.

FAQ

What is the difference between Recursion and Backtracking?

Recursion is the mechanism of a function calling itself. Backtracking is an algorithm that uses Recursion to explore all solutions, abandoning paths that cannot lead to a valid solution.

How do I optimize a Backtracking solution?

Add pruning (check constraints early), sort to handle duplicates efficiently, use bitmasks for visited tracking, and consider symmetry-breaking to reduce search space.

When should I use iteration instead of recursion?

Use iteration when the recursion depth exceeds the call stack limit (typically 1000), when the solution has a natural iterative structure, or when memory is constrained.

Sorting & Searching
Heap, Stack & Queue
DSA Patterns

Built by the developers of Doda Browser, DodaZIP, and Durga Antivirus Pro. Updated 2026-06-23.

← Previous Sorting and Searching Problems — Interview Guide with Solutions Next → Heap, Stack and Queue Problems — Complete Interview Guide

Built by the developers of DodaTech

Doda Browser, DodaZIP & Durga Antivirus Pro

Home Browse Interview Prep