DSA

Recursion & Backtracking

Interview Prep · 7 entries

Base Case & Recursive Case

syntax

Every recursive function needs:
1. Base case: when to stop (prevents infinite recursion)
2. Recursive case: break problem into smaller subproblem
3. Progress: each call must move toward the base case

example

// JavaScript — Sum of array using recursion
function sumArray(arr, idx = 0) {
  if (idx >= arr.length) return 0;      // base case
  return arr[idx] + sumArray(arr, idx + 1); // recursive case
}

// Power function
function power(base, exp) {
  if (exp === 0) return 1;               // base case
  if (exp % 2 === 0) {
    const half = power(base, exp / 2);
    return half * half;                  // O(log n)
  }
  return base * power(base, exp - 1);
}

# Python
def sum_array(arr, idx=0):
    if idx >= len(arr):
        return 0
    return arr[idx] + sum_array(arr, idx + 1)

def power(base, exp):
    if exp == 0:
        return 1
    if exp % 2 == 0:
        half = power(base, exp // 2)
        return half * half
    return base * power(base, exp - 1)

output

sum_array([1,2,3,4]) → 10
power(2, 10) → 1024

Note Always identify the base case first. Stack overflow risk: Python default limit is 1000 frames (sys.setrecursionlimit can increase). For deep recursion, convert to iteration. The power function shows how recursion can achieve O(log n) — a common follow-up.

base caserecursive caserecursion fundamentalsstack overflowrecursive thinking

Permutations

syntax

Generate all orderings of elements.
Backtrack: at each position, try each unused element.
Swap or use a 'used' boolean array to track which elements are placed.

example

// JavaScript
function permute(nums) {
  const result = [];
  function backtrack(current, remaining) {
    if (remaining.length === 0) {
      result.push([...current]);
      return;
    }
    for (let i = 0; i < remaining.length; i++) {
      current.push(remaining[i]);
      backtrack(current, [...remaining.slice(0, i), ...remaining.slice(i + 1)]);
      current.pop(); // undo choice
    }
  }
  backtrack([], nums);
  return result;
}

# Python
def permute(nums):
    result = []
    def backtrack(current, remaining):
        if not remaining:
            result.append(current[:])
            return
        for i in range(len(remaining)):
            current.append(remaining[i])
            backtrack(current, remaining[:i] + remaining[i+1:])
            current.pop()
    backtrack([], nums)
    return result

output

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

Note Time O(n! * n), Space O(n). The 'undo choice' step (current.pop()) is the hallmark of backtracking. For permutations with duplicates: sort first, and skip if nums[i] == nums[i-1] and nums[i-1] was not used in this branch. n! grows extremely fast — practical only for n ≤ ~10.

permutationsgenerate permutationsbacktrackingall orderings

Combinations

syntax

Choose k items from n without regard to order.
Backtrack: at each step, choose to include or exclude the current element.
Only pick elements with index >= start to avoid duplicates.

example

// JavaScript
function combine(n, k) {
  const result = [];
  function backtrack(start, current) {
    if (current.length === k) {
      result.push([...current]);
      return;
    }
    for (let i = start; i <= n; i++) {
      current.push(i);
      backtrack(i + 1, current);
      current.pop();
    }
  }
  backtrack(1, []);
  return result;
}

# Python
def combine(n, k):
    result = []
    def backtrack(start, current):
        if len(current) == k:
            result.append(current[:])
            return
        for i in range(start, n + 1):
            current.append(i)
            backtrack(i + 1, current)
            current.pop()
    backtrack(1, [])
    return result

output

combine(4, 2) → [[1,2],[1,3],[1,4],[2,3],[2,4],[3,4]]

Note Time O(C(n,k) * k), Space O(k) for recursion depth. The key difference from permutations: use a 'start' parameter to only pick forward, preventing duplicate combinations. Optimization: prune when remaining elements < needed elements (n - i + 1 < k - len(current)).

combinationschoose k from nbacktracking combinationsC(n,k)

Subsets (Power Set)

syntax

Generate all 2^n subsets of a set.
Backtrack: for each element, choose to include it or not.
Alternative: iterative bit manipulation.

example

// JavaScript
function subsets(nums) {
  const result = [];
  function backtrack(start, current) {
    result.push([...current]); // every state is a valid subset
    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);
      backtrack(i + 1, current);
      current.pop();
    }
  }
  backtrack(0, []);
  return result;
}

// Iterative approach
function subsetsIterative(nums) {
  const result = [[]];
  for (const num of nums) {
    const newSubsets = result.map(sub => [...sub, num]);
    result.push(...newSubsets);
  }
  return result;
}

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

output

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

Note Time O(2^n * n), Space O(n) recursion depth. Unlike combinations, we add to result at every recursive call (not just when a condition is met). For subsets with duplicates: sort the input, then skip nums[i] == nums[i-1] when i > start. The iterative approach is elegant and avoids recursion.

subsetspower setgenerate subsetsbacktracking subsetsall combinations

N-Queens Concept

syntax

Place n queens on an n×n board so no two attack each other.
Backtrack row by row. For each row, try placing a queen in each column.
Check conflicts: same column, same diagonal (row-col), same anti-diagonal (row+col).

example

// JavaScript
function solveNQueens(n) {
  const results = [];
  const cols = new Set(), diag1 = new Set(), diag2 = new Set();

  function backtrack(row, board) {
    if (row === n) {
      results.push(board.map(r => '.'.repeat(r) + 'Q' + '.'.repeat(n - r - 1)));
      return;
    }
    for (let col = 0; col < n; col++) {
      if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) continue;
      cols.add(col); diag1.add(row - col); diag2.add(row + col);
      board.push(col);
      backtrack(row + 1, board);
      board.pop();
      cols.delete(col); diag1.delete(row - col); diag2.delete(row + col);
    }
  }
  backtrack(0, []);
  return results;
}

# Python
def solve_n_queens(n):
    results = []
    cols, diag1, diag2 = set(), set(), set()

    def backtrack(row, board):
        if row == n:
            results.append(['.' * c + 'Q' + '.' * (n - c - 1) for c in board])
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue
            cols.add(col); diag1.add(row - col); diag2.add(row + col)
            board.append(col)
            backtrack(row + 1, board)
            board.pop()
            cols.discard(col); diag1.discard(row - col); diag2.discard(row + col)
    backtrack(0, [])
    return results

output

solve_n_queens(4) → 2 solutions
['.Q..','...Q','Q...','..Q.'] and ['..Q.','Q...','...Q','.Q..']

Note Time O(n!), Space O(n). The diagonal trick: queens on the same diagonal have the same (row-col), same anti-diagonal have same (row+col). Using sets for O(1) conflict checking is more elegant than iterating over placed queens. This is the canonical backtracking problem.

N-queensqueen placementbacktracking boardconstraint satisfaction

Sudoku Solver Concept

syntax

Fill empty cells one at a time.
For each empty cell, try digits 1-9.
Check row, column, and 3x3 box constraints.
Backtrack if no valid digit fits.

example

// JavaScript
function solveSudoku(board) {
  function isValid(board, row, col, num) {
    const ch = String(num);
    for (let i = 0; i < 9; i++) {
      if (board[row][i] === ch) return false; // row
      if (board[i][col] === ch) return false; // column
      const boxR = 3 * Math.floor(row / 3) + Math.floor(i / 3);
      const boxC = 3 * Math.floor(col / 3) + (i % 3);
      if (board[boxR][boxC] === ch) return false; // box
    }
    return true;
  }

  function solve(board) {
    for (let r = 0; r < 9; r++) {
      for (let c = 0; c < 9; c++) {
        if (board[r][c] === '.') {
          for (let num = 1; num <= 9; num++) {
            if (isValid(board, r, c, num)) {
              board[r][c] = String(num);
              if (solve(board)) return true;
              board[r][c] = '.';
            }
          }
          return false; // no valid digit → backtrack
        }
      }
    }
    return true; // all cells filled
  }
  solve(board);
}

# Python
def solve_sudoku(board):
    def is_valid(row, col, num):
        ch = str(num)
        for i in range(9):
            if board[row][i] == ch: return False
            if board[i][col] == ch: return False
            br = 3 * (row // 3) + i // 3
            bc = 3 * (col // 3) + i % 3
            if board[br][bc] == ch: return False
        return True

    def solve():
        for r in range(9):
            for c in range(9):
                if board[r][c] == '.':
                    for num in range(1, 10):
                        if is_valid(r, c, num):
                            board[r][c] = str(num)
                            if solve(): return True
                            board[r][c] = '.'
                    return False
        return True
    solve()

output

Fills in all '.' cells with valid digits 1-9.

Note Time O(9^(empty cells)) worst case, but pruning makes it much faster in practice. Optimization: use sets for each row, column, and box to check validity in O(1) instead of O(9). Finding the cell with fewest candidates first (MRV heuristic) dramatically speeds up solving.

sudoku solverconstraint propagationbacktracking grid9x9 puzzle

Word Search in Grid

syntax

DFS from each cell. At each step, check if the current cell matches the next character.
Mark cell as visited (temporarily modify it), recurse in 4 directions, then unmark.

example

// JavaScript
function exist(board, word) {
  const rows = board.length, cols = board[0].length;
  function dfs(r, c, idx) {
    if (idx === word.length) return true;
    if (r < 0 || r >= rows || c < 0 || c >= cols) return false;
    if (board[r][c] !== word[idx]) return false;
    const saved = board[r][c];
    board[r][c] = '#'; // mark visited
    const found = dfs(r+1,c,idx+1) || dfs(r-1,c,idx+1)
               || dfs(r,c+1,idx+1) || dfs(r,c-1,idx+1);
    board[r][c] = saved; // 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;
}

# Python
def exist(board, word):
    rows, cols = len(board), len(board[0])
    def dfs(r, c, idx):
        if idx == len(word):
            return True
        if r < 0 or r >= rows or c < 0 or c >= cols:
            return False
        if board[r][c] != word[idx]:
            return False
        saved = board[r][c]
        board[r][c] = '#'
        found = (dfs(r+1,c,idx+1) or dfs(r-1,c,idx+1)
                 or dfs(r,c+1,idx+1) or dfs(r,c-1,idx+1))
        board[r][c] = saved
        return found
    for r in range(rows):
        for c in range(cols):
            if dfs(r, c, 0):
                return True
    return False

output

board = [['A','B','C','E'],
         ['S','F','C','S'],
         ['A','D','E','E']]
exist(board, 'ABCCED') → True

Note Time O(m * n * 4^L) where L = word length. The temporary cell modification is a clean alternative to a separate visited set. Always restore the cell after backtracking. Optimization: check if the board has all needed characters before starting DFS.

word searchgrid DFSbacktracking gridpath finding word