Neetcode 150 Backtracking Interview Notes

Backtracking = DFS + path + undo.

Complexities below exclude the returned output unless mentioned.

For every problem, first ask:

• What is one decision?
• What makes a path valid?
• When do I add to result?
• Do I need to avoid duplicates?
• Can I prune early?

Table of Contents

• Pattern Map
• Pattern 1: Include / Exclude
  • 1. Subsets
  • 2. Subsets II
• Pattern 2: Combination With Target
  • 3. Combination Sum
  • 4. Combination Sum II
• Pattern 3: Arrangement / Ordering
  • 5. Permutations
• Pattern 4: String Partition
  • 6. Palindrome Partitioning
• Pattern 5: Character Expansion
  • 7. Letter Combinations of a Phone Number
• Pattern 6: Grid DFS With Visited Path
  • 8. Word Search
• Pattern 7: Trie + Grid DFS
  • 9. Word Search II
• Pattern 8: Constraint Placement
  • 10. N-Queens

Pattern Map

Pattern	Problems
Pattern 1: Include / exclude	1. Subsets, 2. Subsets II
Pattern 2: Combination with target	3. Combination Sum, 4. Combination Sum II
Pattern 3: Arrangement / ordering	5. Permutations
Pattern 4: String partition	6. Palindrome Partitioning
Pattern 5: Character expansion	7. Letter Combinations of a Phone Number
Pattern 6: Grid DFS with visited path	8. Word Search
Pattern 7: Trie + grid DFS	9. Word Search II
Pattern 8: Constraint placement	10. N-Queens

Pattern 1: Include / Exclude

1. Subsets

• Link: https://neetcode.io/problems/subsets?list=neetcode150
• Problem: Return all possible subsets of a unique integer array.
• Key idea:
  • At every index, make 2 choices:
    • skip current number
    • include current number
  • DFS path represents current subset.
  • Add subset when i === nums.length.

function subsets(nums) {
  const res = [];
  const path = [];
 
  function dfs(i) {
    if (i === nums.length) {
      res.push([...path]);
      return;
    }
 
    dfs(i + 1);
 
    path.push(nums[i]);
    dfs(i + 1);
    path.pop();
  }
 
  dfs(0);
  return res;
}

• Time: O(n * 2^n)
  • 2^n subsets, copying each subset can take up to n.
• Space: O(n)
  • recursion/path space, excluding output.
• Interview note:
  • Clean starter problem.
  • Think: “for each number, do I take it or leave it?“

2. Subsets II

• Link: https://neetcode.io/problems/subsets-ii?list=neetcode150
• Problem: Return all unique subsets when nums can contain duplicates.
• Key idea:
  • Sort first so duplicates are adjacent.
  • Use the same include/exclude tree.
  • After excluding nums[i], skip all same values before continuing.

nums.sort((a, b) => a - b);
 
function dfs(i) {
  if (i === nums.length) {
    res.push([...path]);
    return;
  }
 
  path.push(nums[i]);
  dfs(i + 1);
  path.pop();
 
  while (i + 1 < nums.length && nums[i] === nums[i + 1]) i++;
  dfs(i + 1);
}

• Time: O(n * 2^n)
• Space: O(n), excluding output.
• Interview note:
  • Duplicate subsets are created from the exclude branch.
  • If you choose to skip a value, skip all of its duplicates together.

Pattern 2: Combination With Target

3. Combination Sum

• Link: https://neetcode.io/problems/combination-target-sum?list=neetcode150
• Problem: Return combinations that sum to target. Same number can be reused.
• Key idea:
  • Use dfs(i, total) or dfs(i, remaining).
  • Choice 1: use candidates[i] and stay at same i.
  • Choice 2: skip it and move to i + 1.
  • Stop when remaining is 0.
  • Prune when remaining is negative or i is out of bounds.

function dfs(i, rem) {
  if (rem === 0) {
    res.push([...path]);
    return;
  }
  if (i === candidates.length || rem < 0) return;
 
  path.push(candidates[i]);
  dfs(i, rem - candidates[i]);
  path.pop();
 
  dfs(i + 1, rem);
}

• Time: O(n^h * h), where h = target / min(candidates) in the worst case.
• Space: O(h), excluding output.
• Interview note:
  • Reuse is handled by calling DFS again with the same index.
  • remaining is usually cleaner than carrying total.

4. Combination Sum II

• Link: https://neetcode.io/problems/combination-target-sum-ii?list=neetcode150
• Problem: Return unique combinations that sum to target. Each number can be used once.
• Key idea:
  • Sort first.
  • Use a for-loop from start.
  • Skip duplicates at the same tree level.
  • Move to i + 1 after choosing because each value can be used once.

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

• Time: O(n * 2^n)
• Space: O(n), excluding output.
• Interview note:
  • i > start is the key duplicate guard.
  • It only skips duplicate choices at the same depth, not valid duplicate values from different depths.

Pattern 3: Arrangement / Ordering

5. Permutations

• Link: https://neetcode.io/problems/permutations?list=neetcode150
• Problem: Return all possible orderings of unique numbers.
• Key idea:
  • Order matters, so every unused number can be the next choice.
  • Track used numbers with a Set or boolean array.
  • Add path when path.length === nums.length.

function dfs() {
  if (path.length === nums.length) {
    res.push([...path]);
    return;
  }
 
  for (const num of nums) {
    if (used.has(num)) continue;
    used.add(num);
    path.push(num);
    dfs();
    path.pop();
    used.delete(num);
  }
}

• Time: O(n! * n)
• Space: O(n), excluding output.
• Interview note:
  • Subsets move left to right using an index.
  • Permutations repeatedly scan all unused choices because order matters.

Pattern 4: String Partition

6. Palindrome Partitioning

• Link: https://neetcode.io/problems/palindrome-partitioning?list=neetcode150
• Problem: Split string into all partitions where every piece is a palindrome.
• Key idea:
  • At index start, try every possible end index.
  • Only choose substring s[start...end] if it is palindrome.
  • Add path when start === s.length.

function dfs(start) {
  if (start === s.length) {
    res.push([...path]);
    return;
  }
 
  for (let end = start; end < s.length; end++) {
    if (!isPal(start, end)) continue;
    path.push(s.slice(start, end + 1));
    dfs(end + 1);
    path.pop();
  }
}

• Time: O(n * 2^n)
  • There are exponential partitions; palindrome checks and substring copies add the n factor.
• Space: O(n), excluding output.
• Interview note:
  • This is not “choose char or skip char”.
  • It is “choose the next valid cut”.

Pattern 5: Character Expansion

7. Letter Combinations of a Phone Number

• Link: https://neetcode.io/problems/letter-combinations-of-a-phone-number?list=neetcode150
• Problem: Return all strings represented by phone keypad digits.
• Key idea:
  • Each digit maps to 3 or 4 letters.
  • At index i, choose one letter from map[digits[i]].
  • Add path when i === digits.length.

function dfs(i) {
  if (i === digits.length) {
    res.push(path.join(""));
    return;
  }
 
  for (const ch of map[digits[i]]) {
    path.push(ch);
    dfs(i + 1);
    path.pop();
  }
}

• Time: O(n * 4^n)
• Space: O(n), excluding output.
• Interview note:
  • This is the simplest “branch by choices” problem.
  • Branching factor is max 4 because digits 7 and 9 have 4 letters.

Pattern 6: Grid DFS With Visited Path

8. Word Search

• Link: https://neetcode.io/problems/search-for-word?list=neetcode150
• Problem: Check if a word exists in a grid by moving up/down/left/right without reusing a cell in the same path.
• Key idea:
  • Start DFS from every cell.
  • DFS state: (r, c, i) where i is current word index.
  • Return true when i === word.length.
  • Mark current cell visited, explore 4 directions, then unmark.

function dfs(r, c, i) {
  if (i === word.length) return true;
  if (
    r < 0 || c < 0 ||
    r === rows || c === cols ||
    board[r][c] !== word[i] ||
    seen.has(`${r},${c}`)
  ) return false;
 
  seen.add(`${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);
  seen.delete(`${r},${c}`);
 
  return found;
}

• Time: O(m * n * 4 * 3^(L - 1))
  • L = word.length.
  • After first step, usually 3 choices because you cannot go back to the previous cell.
• Space: O(L)
• Interview note:
  • visited is path-specific, not globally permanent.
  • Always undo before returning from that DFS path.

Pattern 7: Trie + Grid DFS

9. Word Search II

• Link: https://neetcode.io/problems/word-search-ii?list=neetcode150
• Problem: Find all dictionary words present in the grid.
• Key idea:
  • Build a Trie from words.
  • DFS from every cell.
  • Move only if current char exists in Trie node.
  • When Trie node has a word, add it to result.
  • Mark found word as null to avoid duplicates.

function dfs(r, c, node) {
  const key = `${r},${c}`;
  if (
    r < 0 || c < 0 ||
    r === rows || c === cols ||
    seen.has(key)
  ) return;
 
  const ch = board[r][c];
  if (!node.children[ch]) return;
 
  node = node.children[ch];
  if (node.word) {
    res.push(node.word);
    node.word = null;
  }
 
  seen.add(key);
  dfs(r + 1, c, node);
  dfs(r - 1, c, node);
  dfs(r, c + 1, node);
  dfs(r, c - 1, node);
  seen.delete(key);
}

• Time: O(m * n * 4 * 3^(L - 1)) worst case, where L is max word length.
• Space: O(totalChars + L)
  • Trie storage plus DFS path.
• Interview note:
  • The Trie is the pruning structure.
  • Without Trie, running Word Search for every word is usually too slow.

Pattern 8: Constraint Placement

10. N-Queens

• Link: https://neetcode.io/problems/n-queens?list=neetcode150
• Problem: Place n queens on an n x n board so none attack each other.
• Key idea:
  • Place exactly one queen per row.
  • Try every column in current row.
  • Track invalid columns and diagonals.
  • Diagonal formulas:
    • positive diagonal: r + c
    • negative diagonal: r - c

function backtrack(r) {
  if (r === n) {
    res.push(board.map(row => row.join("")));
    return;
  }
 
  for (let c = 0; c < n; c++) {
    if (cols.has(c) || posDiag.has(r + c) || negDiag.has(r - c)) continue;
 
    cols.add(c);
    posDiag.add(r + c);
    negDiag.add(r - c);
    board[r][c] = "Q";
 
    backtrack(r + 1);
 
    cols.delete(c);
    posDiag.delete(r + c);
    negDiag.delete(r - c);
    board[r][c] = ".";
  }
}

• Time: O(n!)
• Space: O(n^2)
  • board storage; sets/recursion are O(n).
• Interview note:
  • Row-by-row removes the need to check rows.
  • Sets make validity checks O(1).