Top Recursion and Backtracking Interview Questions & Solutions (2026)

1. Introduction to Backtracking & Recursion

Backtracking is a search algorithm that explores all possible configuration states of a problem (often modeled as a State-Space Tree).

The Standard 3-Step Backtracking Blueprint:

function backtrack(state, choices):
    if state is a valid solution:
        add state to results
        return

    for choice in choices:
        if choice is valid:
            make choice (modify state)
            backtrack(new_state, remaining_choices)
            undo choice (BACKTRACK / revert state)

2. Core Interview Questions & Verified Solutions

Q1. Subsets (Power Set Generation)

Problem Statement: Given an integer array nums of unique elements, return all possible subsets (the power set).

python
def subsets(nums: list[int]) -> list[list[int]]:
    result = []
    
    def backtrack(start_index, current_subset):
        result.append(list(current_subset))
        
        for i in range(start_index, len(nums)):
            current_subset.append(nums[i])
            backtrack(i + 1, current_subset)
            current_subset.pop() # Backtrack
            
    backtrack(0, [])
    return result

• Time Complexity: O(N · 2^N) | Space Complexity: O(N) stack space.

Q2. Permutations

Problem Statement: Given an array nums of distinct integers, return all possible permutations.

cpp
#include <vector>

void backtrack(std::vector<int>& nums, int start, std::vector<std::vector<int>>& result) {
    if (start == nums.size()) {
        result.push_back(nums);
        return;
    }
    for (int i = start; i < nums.size(); i++) {
        std::swap(nums[start], nums[i]);
        backtrack(nums, start + 1, result);
        std::swap(nums[start], nums[i]); // Backtrack
    }
}

std::vector<std::vector<int>> permute(std::vector<int>& nums) {
    std::vector<std::vector<int>> result;
    backtrack(nums, 0, result);
    return result;
}

• Time Complexity: O(N · N!) | Space Complexity: O(N) stack space.

Q3. Combination Sum

Problem Statement: Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations where the chosen numbers sum to target. Elements may be chosen unlimited times.

java
import java.util.*;

class Solution {
    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        List<List<Integer>> result = new ArrayList<>();
        Arrays.sort(candidates);
        backtrack(candidates, target, 0, new ArrayList<>(), result);
        return result;
    }

    private void backtrack(int[] candidates, int remain, int start, List<Integer> current, List<List<Integer>> result) {
        if (remain == 0) {
            result.add(new ArrayList<>(current));
            return;
        }
        for (int i = start; i < candidates.length; i++) {
            if (candidates[i] > remain) break; // Pruning!
            current.add(candidates[i]);
            backtrack(candidates, remain - candidates[i], i, current, result); // reuse same element i
            current.remove(current.size() - 1); // Backtrack
        }
    }
}

• Time Complexity: O(2^{target}) worst-case | Space Complexity: O(target) stack depth.

Q4. Word Search (2D Grid Backtracking)

Problem Statement: Given an M × N grid of characters board and a string word, return true if word exists in the grid.

javascript
function exist(board, word) {
    const rows = board.length;
    const cols = board[0].length;

    function dfs(r, c, index) {
        if (index === word.length) return true;
        if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] !== word[index]) {
            return false;
        }

        const temp = board[r][c];
        board[r][c] = '#'; // Mark visited

        const found = dfs(r + 1, c, index + 1) ||
                      dfs(r - 1, c, index + 1) ||
                      dfs(r, c + 1, index + 1) ||
                      dfs(r, c - 1, index + 1);

        board[r][c] = temp; // Backtrack / unmark
        return found;
    }

    for (let r = 0; r < rows; r++) {
        for (let c = 0; c < cols; c++) {
            if (dfs(r, c, 0)) return true;
        }
    }
    return false;
}

• Time Complexity: O(M · N · 4^L) where L = word length | Space Complexity: O(L) recursion stack.

Q5. N-Queens Problem

Problem Statement: Place N chess queens on an N × N chessboard such that no two queens attack each other.

python
def solveNQueens(n: int) -> list[list[str]]:
    cols = set()
    pos_diag = set() # (r + c)
    neg_diag = set() # (r - c)
    result = []
    board = [["."] * n for _ in range(n)]

    def backtrack(r):
        if r == n:
            result.append(["".join(row) for row in board])
            return

        for c in range(n):
            if c in cols or (r + c) in pos_diag or (r - c) in neg_diag:
                continue

            cols.add(c)
            pos_diag.add(r + c)
            neg_diag.add(r - c)
            board[r][c] = "Q"

            backtrack(r + 1)

            cols.remove(c)
            pos_diag.remove(r + c)
            neg_diag.remove(r - c)
            board[r][c] = "."

    backtrack(0)
    return result

• Time Complexity: O(N!) | Space Complexity: O(N) sets and board storage.

3. Backtracking Pattern Cheat Sheet

Practice all recursion & backtracking coding problems on DSAMaster's practice platform.