Tracks

Full-Stack Interview Prep

BackTracking

18 problems · 20 approaches

Print all Subsequences of a stringMedium2 approaches

Problem

Print all 2^n subsequences of the string (keep or skip each character, preserving order), including the empty one.

Example 1

Input:  "abc"
Output: "", a, b, c, ab, ac, bc, abc

Also asked as: subsets · print all subsets

1. Backtracking (choose / un-choose)

Time O(2ⁿ · n)Space O(n) recursion

At each index, branch: include the element, recurse, then remove it and recurse again.

function subsets(arr) {
  const res = [], path = [];
  const bt = (start) => {
    res.push([...path]);
    for (let i = start; i < arr.length; i++) {
      path.push(arr[i]);
      bt(i + 1);
      path.pop();
    }
  };
  bt(0);
  return res;
}

2. Bitmask enumeration

Time O(2ⁿ · n)Space O(1) extra

Each subset maps to a number 0..2ⁿ−1; bit j set ⇒ include element j. No recursion.

function subsets(arr) {
  const n = arr.length, res = [];
  for (let mask = 0; mask < (1 << n); mask++) {
    const sub = [];
    for (let j = 0; j < n; j++) if (mask & (1 << j)) sub.push(arr[j]);
    res.push(sub);
  }
  return res;
}

Print all the permutations of the given stringMedium2 approaches

Problem

Print every ordering of the string's characters. If characters repeat, print each distinct permutation only once.

Example 1

Input:  "abc"
Output: abc, acb, bac, bca, cab, cba

Example 2

Input:  "aab"
Output: aab, aba, baa

Also asked as: permutations · Print all permutations of a string

1. Backtracking with a used[] array

Time O(n! · n)Space O(n)

Pick an unused element for the current position, recurse, then release it.

function permutations(arr) {
  const res = [], path = [], used = Array(arr.length).fill(false);
  const bt = () => {
    if (path.length === arr.length) { res.push([...path]); return; }
    for (let i = 0; i < arr.length; i++) {
      if (used[i]) continue;
      used[i] = true; path.push(arr[i]);
      bt();
      path.pop(); used[i] = false;
    }
  };
  bt();
  return res;
}

2. In-place swap

Time O(n! · n)Space O(n)

Fix each element into the first position by swapping, recurse on the rest, swap back.

function permutations(arr) {
  const res = [];
  const bt = (k) => {
    if (k === arr.length) { res.push([...arr]); return; }
    for (let i = k; i < arr.length; i++) {
      [arr[k], arr[i]] = [arr[i], arr[k]];
      bt(k + 1);
      [arr[k], arr[i]] = [arr[i], arr[k]];
    }
  };
  bt(0);
  return res;
}

Rat in a maze — print all pathsMedium1 approach

Problem

A rat starts at (0, 0) of an n × n grid (1 = open, 0 = blocked) and must reach (n−1, n−1). It moves U, D, L or R and cannot revisit a cell. Return every path as a string of moves, in lexicographic order.

Example 1

Input:  [[1,0,0,0], [1,1,0,1], [1,1,0,0], [0,1,1,1]]
Output: ["DDRDRR", "DRDDRR"]

Also asked as: Rat in a maze Problem · Find shortest safe route in a path with landmines

1. DFS with a visited mark, path string, undo on return

Time O(4^(R·C))Space O(R·C)

From (0,0) try moves D,L,R,U (order defines lexical output); mark the cell, recurse, unmark. Record the path when you reach the target.

function ratMaze(grid) {
  const n = grid.length, res = [];
  const vis = Array.from({ length: n }, () => Array(n).fill(false));
  const dirs = [[1, 0, 'D'], [0, -1, 'L'], [0, 1, 'R'], [-1, 0, 'U']];
  const bt = (r, c, path) => {
    if (r === n - 1 && c === n - 1) { res.push(path); return; }
    for (const [dr, dc, ch] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nc >= 0 && nr < n && nc < n && !vis[nr][nc] && grid[nr][nc] === 1) {
        vis[nr][nc] = true;
        bt(nr, nc, path + ch);
        vis[nr][nc] = false;
      }
    }
  };
  if (grid[0][0] === 1) { vis[0][0] = true; bt(0, 0, ''); }
  return res;
}

Shortest safe route with landmines: mark every cell adjacent to a mine as unsafe first, then either backtrack tracking the best length, or BFS for the true shortest.

N-Queens — all solutionsHard1 approach

Problem

Place n queens on an n × n board so that no two attack each other (same row, column or diagonal). Return every distinct board.

Example 1

Input:  n = 4
Output: [".Q..","...Q","Q...","..Q."] and ["..Q.","Q...","...Q",".Q.."]

Also asked as: Printing all solutions in N-Queen Problem

1. Row-by-row with column & diagonal sets

Time O(N!)Space O(N)

Place one queen per row. A column is free if it is not in `cols`, and diagonals are tracked by r−c and r+c. Recurse, backtrack.

function solveNQueens(n) {
  const res = [], pos = [];
  const cols = new Set(), d1 = new Set(), d2 = new Set();
  const bt = (r) => {
    if (r === n) { res.push(pos.map((c) => '.'.repeat(c) + 'Q' + '.'.repeat(n - c - 1))); return; }
    for (let c = 0; c < n; c++) {
      if (cols.has(c) || d1.has(r - c) || d2.has(r + c)) continue;
      cols.add(c); d1.add(r - c); d2.add(r + c); pos.push(c);
      bt(r + 1);
      cols.delete(c); d1.delete(r - c); d2.delete(r + c); pos.pop();
    }
  };
  bt(0);
  return res;
}

Sudoku solverHard1 approach

Problem

Fill the empty cells (".") of a 9 × 9 Sudoku so that each row, each column and each 3 × 3 box contains the digits 1–9 exactly once. The puzzle has exactly one solution.

Example 1

Input:  a partially filled 9 × 9 board
Output: the completed board

Also asked as: Sudoku Solver

1. Fill the first empty cell, try 1–9, recurse

Time exponential (fast in practice)Space O(1)

For each empty cell try every digit that is valid in its row, column and 3×3 box; recurse; undo if the branch fails.

function solveSudoku(board) {
  const valid = (r, c, ch) => {
    for (let i = 0; i < 9; i++) {
      if (board[r][i] === ch || board[i][c] === ch) return false;
      const br = 3 * ((r / 3) | 0) + ((i / 3) | 0);
      const bc = 3 * ((c / 3) | 0) + (i % 3);
      if (board[br][bc] === ch) return false;
    }
    return true;
  };
  const bt = () => {
    for (let r = 0; r < 9; r++)
      for (let c = 0; c < 9; c++) {
        if (board[r][c] !== '.') continue;
        for (let d = 1; d <= 9; d++) {
          const ch = String(d);
          if (valid(r, c, ch)) {
            board[r][c] = ch;
            if (bt()) return true;
            board[r][c] = '.';
          }
        }
        return false;
      }
    return true;
  };
  bt();
  return board;
}

Remove minimum invalid parenthesesHard1 approach

Problem

Remove the minimum number of parentheses to make the string valid, and return every distinct valid result. The string may also contain letters.

Example 1

Input:  "()())()"
Output: ["(())()", "()()()"]

Example 2

Input:  "(a)())()"
Output: ["(a())()", "(a)()()"]

Also asked as: Remove Invalid Parentheses

1. BFS by removal count

Time O(2ⁿ) worstSpace O(2ⁿ)

Level 0 = the original string; each level removes one character. Return all valid strings from the first level that contains any — that is the minimum number of removals.

function removeInvalidParentheses(s) {
  const isValid = (str) => {
    let bal = 0;
    for (const c of str) {
      if (c === '(') bal++;
      else if (c === ')' && --bal < 0) return false;
    }
    return bal === 0;
  };
  let level = new Set([s]);
  while (level.size) {
    const valid = [...level].filter(isValid);
    if (valid.length) return valid;
    const next = new Set();
    for (const str of level)
      for (let i = 0; i < str.length; i++)
        if (str[i] === '(' || str[i] === ')') next.add(str.slice(0, i) + str.slice(i + 1));
    level = next;
  }
  return [''];
}

Print all palindromic partitions of a stringMedium1 approach

Problem

Split the string into pieces so that every piece is a palindrome. Return every such split.

Example 1

Input:  "aab"
Output: [["a","a","b"], ["aa","b"]]

Also asked as: Print all palindromic partitions of a string

1. Backtrack over cut positions

Time O(2ⁿ · n)Space O(n)

For each prefix that is a palindrome, add it to the current partition and recurse on the rest.

function partitionPalindromes(s) {
  const res = [], path = [];
  const isPal = (l, r) => { while (l < r) if (s[l++] !== s[r--]) return false; return true; };
  const bt = (start) => {
    if (start === s.length) { res.push([...path]); return; }
    for (let end = start; end < s.length; end++) {
      if (isPal(start, end)) {
        path.push(s.slice(start, end + 1));
        bt(end + 1);
        path.pop();
      }
    }
  };
  bt(0);
  return res;
}

Subset sum — does any subset add up to the target?Medium1 approach

Problem

Given non-negative integers and a target sum, return true if some subset of them adds up exactly to the target.

Example 1

Input:  arr = [3, 34, 4, 12, 5, 2], sum = 9
Output: true

4 + 5.

Example 2

Input:  same, sum = 30
Output: false

Also asked as: Subset Sum Problem · Partition of a set intoK subsets with equal sum · Tug of War

1. Include / exclude with pruning

Time O(2ⁿ)Space O(n)

At each index either take the number (if it fits) or skip it. Prune when the remaining sum cannot reach the target.

function subsetSum(nums, target) {
  const bt = (i, remaining) => {
    if (remaining === 0) return true;
    if (i === nums.length || remaining < 0) return false;
    return bt(i + 1, remaining - nums[i]) || bt(i + 1, remaining);
  };
  return bt(0, target);
}

Partition into k equal-sum subsets: check total % k === 0, then try to fill k buckets to total/k with backtracking (sort desc, skip duplicate bucket states). Tug of War: split into two halves of size n/2 minimising the sum difference.

The Knight's tourHard1 approach

Problem

Move a knight around an n × n board so that it visits every square exactly once. Return the board with each square numbered by its visiting order (the backtracking version is usually shown with n = 8).

Example 1

Input:  n = 5, start (0, 0)
Output: a 5 × 5 grid numbered 0..24 in knight-move order

Also asked as: The Knight’s tour problem

1. DFS numbering squares; backtrack on dead ends

Time exponential (Warnsdorff heuristic makes it fast)Space O(N²)

From the current square, try all 8 knight moves to an unvisited in-bounds square; mark it with the move number; recurse; unmark on failure.

function knightTour(N) {
  const board = Array.from({ length: N }, () => Array(N).fill(-1));
  const moves = [[2,1],[1,2],[-1,2],[-2,1],[-2,-1],[-1,-2],[1,-2],[2,-1]];
  board[0][0] = 0;
  const bt = (r, c, step) => {
    if (step === N * N) return true;
    for (const [dr, dc] of moves) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nc >= 0 && nr < N && nc < N && board[nr][nc] === -1) {
        board[nr][nc] = step;
        if (bt(nr, nc, step + 1)) return true;
        board[nr][nc] = -1;
      }
    }
    return false;
  };
  return bt(0, 0, 1) ? board : null;
}

Combination SumMedium1 approach

Problem

Given distinct positive candidates and a target, return every unique combination of candidates that sums to target. Each candidate may be used any number of times, and combinations that differ only in order count once.

Example 1

Input:  candidates = [2, 3, 6, 7], target = 7
Output: [[2, 2, 3], [7]]

Also asked as: Combinational Sum

1. Backttrack, allowing reuse (recurse on the same index)

Time O(2^target)Space O(target / min)

From `start`, try each candidate; subtract it from the target and recurse on `i` (reuse allowed) or `i+1` (no reuse). Sort to prune once a candidate exceeds the remaining target.

function combinationSum(candidates, target) {
  candidates.sort((a, b) => a - b);
  const res = [], path = [];
  const bt = (start, remaining) => {
    if (remaining === 0) { res.push([...path]); return; }
    for (let i = start; i < candidates.length && candidates[i] <= remaining; i++) {
      path.push(candidates[i]);
      bt(i, remaining - candidates[i]); // i (not i+1) ⇒ reuse allowed
      path.pop();
    }
  };
  bt(0, target);
  return res;
}

Maximum number by doing at most K swapsMedium1 approach

Problem

Given a number as a string, swap any two digits at most k times to make the largest possible number. Return it.

Example 1

Input:  s = "1234567", k = 4
Output: "7654321"

Example 2

Input:  s = "3435335", k = 3
Output: "5543333"

Also asked as: Find Maximum number possible by doing at-most K swaps

1. Backtracking — at each position bring the largest reachable digit forward

Time O(n^k) worstSpace O(n)

For each position, find the max digit to its right; try swapping it in (spending a swap) and recurse. Track the best string seen. Only swap when it actually increases the number.

function maxNumberKSwaps(numStr, k) {
  const digits = [...numStr];
  let best = numStr;
  const bt = (idx, swaps) => {
    if (swaps === 0 || idx === digits.length) return;
    const maxDigit = Math.max(...digits.slice(idx).map(Number));
    for (let j = digits.length - 1; j > idx; j--) {
      if (Number(digits[j]) === maxDigit && digits[j] !== digits[idx]) {
        [digits[idx], digits[j]] = [digits[j], digits[idx]];
        const cur = digits.join('');
        if (cur > best) best = cur;
        bt(idx + 1, swaps - 1);
        [digits[idx], digits[j]] = [digits[j], digits[idx]];
      }
    }
    bt(idx + 1, swaps); // also allow not swapping at this position
  };
  bt(0, k);
  return best;
}

Longest route in a matrix with hurdles / all paths top-left to bottom-rightMedium1 approach

Problem

(1) Longest route: in a grid of 1 (open) and 0 (hurdle), return the length of the longest path from source to destination that never revisits a cell, or −1 if there is none. (2) All paths: print every path from the top-left to the bottom-right corner of an m × n grid, moving only right or down.

Example 1

Input:  all paths in [[1,2,3], [4,5,6]]
Output: 1 4 5 6, 1 2 5 6, 1 2 3 6

Also asked as: Longest Possible Route in a Matrix with Hurdles · Print all possible paths from top left to bottom right of a mXn matrix

1. DFS with a visited grid, maximise / collect on reaching the target

Time O(4^(R·C))Space O(R·C)

From each cell recurse into the 4 open, unvisited, in-bounds neighbours; mark on entry, unmark on exit. Track the longest length (or push the path) when you hit the destination.

function longestRoute(grid, sr, sc, dr, dc) {
  const R = grid.length, C = grid[0].length;
  const vis = Array.from({ length: R }, () => Array(C).fill(false));
  let best = -1;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  const dfs = (r, c, len) => {
    if (r === dr && c === dc) { best = Math.max(best, len); return; }
    for (const [ddr, ddc] of dirs) {
      const nr = r + ddr, nc = c + ddc;
      if (nr >= 0 && nc >= 0 && nr < R && nc < C && grid[nr][nc] === 1 && !vis[nr][nc]) {
        vis[nr][nc] = true;
        dfs(nr, nc, len + 1);
        vis[nr][nc] = false;
      }
    }
  };
  vis[sr][sc] = true;
  dfs(sr, sc, 0);
  return best;
}

All paths (only moving right/down) is simpler: recurse pushing "R"/"D" until you reach (m−1, n−1).

Kth permutation sequence of 1..NMedium1 approach

Problem

The n! permutations of [1..n] are listed in lexicographic order. Return the kth one (1-indexed) without generating the others.

Example 1

Input:  n = 3, k = 3
Output: "213"

123, 132, 213, …

Example 2

Input:  n = 4, k = 9
Output: "2314"

Also asked as: Find the K-th Permutation Sequence of first N natural numbers

1. Factorial number system (no enumeration)

Time O(n²)Space O(n)

The first digit is determined by k / (n−1)!; remove it, take k mod (n−1)!, repeat. O(n²) without generating permutations.

function getPermutation(n, k) {
  const fact = [1];
  for (let i = 1; i <= n; i++) fact[i] = fact[i - 1] * i;
  const digits = Array.from({ length: n }, (_, i) => i + 1);
  k--; // 0-indexed
  let res = '';
  for (let i = n; i >= 1; i--) {
    const idx = Math.floor(k / fact[i - 1]);
    res += digits[idx];
    digits.splice(idx, 1);
    k %= fact[i - 1];
  }
  return res;
}

Subsets IIMedium1 approach

Problem

The array may contain duplicates. Return every possible subset, with no duplicate subsets in the result.

Example 1

Input:  [1, 2, 2]
Output: [[], [1], [1,2], [1,2,2], [2], [2,2]]

1. Sort + skip equal siblings

Time O(n · 2^n)Space O(n)

Sort so duplicates are adjacent. At one recursion level, use a repeated value only for its first occurrence (i > start && nums[i] === nums[i − 1] → skip).

function subsetsWithDup(nums) {
  nums.sort((a, b) => a - b);
  const res = [], path = [];
  const bt = (start) => {
    res.push([...path]);
    for (let i = start; i < nums.length; i++) {
      if (i > start && nums[i] === nums[i - 1]) continue;
      path.push(nums[i]);
      bt(i + 1);
      path.pop();
    }
  };
  bt(0);
  return res;
}

Combination Sum IIMedium1 approach

Problem

Return every unique combination of candidates that sums to target. Each candidate may be used at most once, and the candidates may contain duplicates, but the result must not contain duplicate combinations.

Example 1

Input:  candidates = [10, 1, 2, 7, 6, 1, 5], target = 8
Output: [[1,1,6], [1,2,5], [1,7], [2,6]]

1. Sort + skip duplicates + prune

Time O(2^n) worst caseSpace O(n)

Each number used at most once (recurse on i + 1). Skip equal siblings like Subsets II, and stop the loop once a candidate exceeds the remaining target.

function combinationSum2(cands, target) {
  cands.sort((a, b) => a - b);
  const res = [], path = [];
  const bt = (start, rem) => {
    if (rem === 0) { res.push([...path]); return; }
    for (let i = start; i < cands.length && cands[i] <= rem; i++) {
      if (i > start && cands[i] === cands[i - 1]) continue;
      path.push(cands[i]);
      bt(i + 1, rem - cands[i]);
      path.pop();
    }
  };
  bt(0, target);
  return res;
}

Letter Combinations of a Phone NumberMedium1 approach

Problem

Given a string of digits 2–9, return every letter combination they could represent on a phone keypad (2 = abc, 3 = def, …, 9 = wxyz).

Example 1

Input:  "23"
Output: ["ad","ae","af","bd","be","bf","cd","ce","cf"]

1. Backtracking over digits

Time O(4^n · n)Space O(n)

One recursion level per digit, one branch per letter on that key.

function letterCombinations(digits) {
  if (!digits) return [];
  const map = ['', '', 'abc', 'def', 'ghi', 'jkl', 'mno', 'pqrs', 'tuv', 'wxyz'];
  const res = [];
  const bt = (i, cur) => {
    if (i === digits.length) { res.push(cur); return; }
    for (const ch of map[digits[i]]) bt(i + 1, cur + ch);
  };
  bt(0, '');
  return res;
}

Generate ParenthesesMedium1 approach

Problem

Return every well-formed string made of n pairs of parentheses.

Example 1

Input:  n = 3
Output: ["((()))", "(()())", "(())()", "()(())", "()()()"]

1. Backtracking with open/close counts

Time O(4^n / √n) — the nth Catalan numberSpace O(n)

Add "(" while fewer than n are open; add ")" only while it would not exceed the opens. Every leaf is valid — no filtering needed.

function generateParenthesis(n) {
  const res = [];
  const bt = (cur, open, close) => {
    if (cur.length === 2 * n) { res.push(cur); return; }
    if (open < n) bt(cur + '(', open + 1, close);
    if (close < open) bt(cur + ')', open, close + 1);
  };
  bt('', 0, 0);
  return res;
}

Word SearchMedium1 approach

Problem

Return true if the word can be spelled in the grid by a path of adjacent cells (up, down, left or right), using each cell at most once.

Example 1

Input:  board = [["A","B","C","E"], ["S","F","C","S"], ["A","D","E","E"]], word = "ABCCED"
Output: true

Example 2

Input:  same board, word = "ABCB"
Output: false

1. DFS with in-place visited marking

Time O(R·C·3^L)Space O(L)

Start from each cell matching word[0]; mark the cell, try four neighbours for the next char, and restore it on return.

function exist(board, word) {
  const R = board.length, C = board[0].length;
  const dfs = (r, c, i) => {
    if (i === word.length) return true;
    if (r < 0 || c < 0 || r >= R || c >= C || board[r][c] !== word[i]) return false;
    const ch = board[r][c];
    board[r][c] = '#';
    const found = dfs(r + 1, c, i + 1) || dfs(r - 1, c, i + 1) || dfs(r, c + 1, i + 1) || dfs(r, c - 1, i + 1);
    board[r][c] = ch;
    return found;
  };
  for (let r = 0; r < R; r++) for (let c = 0; c < C; c++) if (dfs(r, c, 0)) return true;
  return false;
}

Pruning: return false early if the board lacks enough of some letter in the word.