DSA for Interviews, From Zero

Part 8 · Lesson 34 · read

Backtracking

Choose, try, then undo. Examples: combination sum, N-Queens, word search.

On this page

  1. Backtracking = depth-first search plus pruning (cutting off bad branches)
  2. The template
  3. Combination sum: reuse allowed
  4. Traced: combination sum for target 7
  5. Palindrome partitioning: where to cut
  6. Word search: backtracking on a grid
  7. N-Queens: pruning with three Sets
  8. Why pruning matters, and what it costs
  9. Practice questions (7)
  10. Make it stick
  11. Part 8 complete: what's next

Backtracking = depth-first search plus pruning (cutting off bad branches)

Lesson 33 made every subset or permutation. Backtracking is also called depth-first search on a tree of choices: you follow one branch as deep as it goes before you try the next one. Real problems usually want only the answers that follow a rule (a constraint). For example: numbers that add up to a target, cuts where every piece is a palindrome, or queens that do not attack each other. It would be a waste to walk the whole tree and filter at the end. Backtracking checks the rule while building the answer. As soon as a partial answer cannot work any more, it drops that branch and steps back (“backtracks”) to try the next choice. Cutting off a branch early is called pruning, like cutting a dead branch off a real tree.

There is nothing new in how it works. It is the same choose, explore, un-choose loop from Lesson 33, with one extra line that says “this choice is no good, skip it”.

The template

JavaScript
function backtrack(state) {  if (isComplete(state)) { save(state); return; }      // 1. a full answer: save it  for (const choice of choicesFrom(state)) {    if (!isValid(state, choice)) continue;             // 2. PRUNE: skip a choice that can never lead to an answer    apply(state, choice);                              // 3. choose    backtrack(state);                                  // 4. explore    undo(state, choice);                               // 5. un-choose (undo)  }}

For any new problem, answer five questions and the code is easy to write. What is the state (the path so far)? When is it complete (then save it)? What are the choices at each step? Which choices are not allowed (prune them)? How do I undo a choice?

Combination sum: reuse allowed

You get different positive numbers and a target. Find every combination that adds up to the target. A number may be used any number of times. The state is the path and the remaining amount. It is complete when remaining === 0. Prune any number that is larger than remaining. Two details make the code correct and fast.

  • Make the recursive call with i, not i + 1, so the same number can be chosen again. But never look backwards (start only moves forward). Then [2, 3] and [3, 2] are not both made.
  • Sort first. Then, when one number is too big, you can use break (stop the whole loop) instead of continue (skip only this number), because all later numbers are bigger.
JavaScript
function combinationSum(candidates, target) {  candidates = [...candidates].sort((a, b) => a - b);        // sorting lets us stop early  const out = [], path = [];  function go(start, remaining) {    if (remaining === 0) { out.push([...path]); return; }    // we reached the target exactly    for (let i = start; i < candidates.length; i++) {      if (candidates[i] > remaining) break;                  // prune: this value and every larger value is too big      path.push(candidates[i]);      go(i, remaining - candidates[i]);                      // i, not i + 1: the same number may be used again      path.pop();    }  }  go(0, target);  return out;}console.log(JSON.stringify(combinationSum([2, 3, 6, 7], 7))); // [[2,2,3],[7]]console.log(JSON.stringify(combinationSum([2, 3, 5], 8)));    // [[2,2,2,2],[2,3,3],[3,5]]console.log(JSON.stringify(combinationSum([2], 1)));          // []

Traced: combination sum for target 7

step 1 / 29
Set up
out = [], path = []

path holds the numbers chosen so far. We want paths that add up to 7.

1const nums = [2, 3, 6, 7], target = 7;▶const out = [], path = [];3function go(start, remaining) {4  if (remaining === 0) { out.push([...path]); return; }5  for (let i = start; i < nums.length; i++) {6    if (nums[i] > remaining) break;7    path.push(nums[i]);8    go(i, remaining - nums[i]);9    path.pop();10  }11}12go(0, target);13console.log(out);
Variables
nums[2, 3, 6, 7]
target7
path[]
out[]
Console
(nothing printed yet)
Choose, recurse, undo. A “prune” step ends a loop early because none of the remaining numbers can fit. · interactive
Dry run · candidates [2, 3, 6, 7], target 7
PathremainingWhat happens
[]7try 2, 3, 6, 7 in turn
[2]5try 2, 3 (6 is too big)
[2, 2]3try 2, 3 (6 is too big)
[2, 2, 2]12 > 1: prune, dead end
[2, 2, 3]0save → answer
[2, 3]23 > 2: prune, dead end
[3]4try 3 (6 is too big)
[3, 3]13 > 1: prune, dead end
[6]16 > 1: prune, dead end
[7]0save → answer

The whole search is just 10 calls (one for each row above). A walk without pruning would make dozens.

Palindrome partitioning: where to cut

Split a string into pieces so that every piece is a palindrome (a word that reads the same forwards and backwards, like “aba”). At each position the choice is how long the next piece is. The pruning rule is to choose only a piece that is a palindrome. When the start reaches the end of the string, every piece so far was valid, so the path is an answer.

JavaScript
function partition(s) {  const out = [], path = [];  const isPal = (l, r) => {    while (l < r) if (s[l++] !== s[r--]) return false;    return true;  };  function go(start) {    if (start === s.length) { out.push([...path]); return; }   // we cut the whole string: one answer    for (let end = start; end < s.length; end++) {      if (!isPal(start, end)) continue;                        // prune: only cut when the piece is a palindrome      path.push(s.slice(start, end + 1));      go(end + 1);      path.pop();    }  }  go(0);  return out;}console.log(JSON.stringify(partition("aab"))); // [["a","a","b"],["aa","b"]]

Word search: backtracking on a grid

Is a word hidden in a grid of letters? You can move up, down, left or right, and you cannot use a cell twice. From each starting cell, try to match the next letter in each of the four directions. The special part is marking cells as used. When you step on a cell, change it to a placeholder (a temporary marker value, here "#"). When you leave, put the letter back. That is the un-choose step. Stop that path at once when the cell is outside the grid, already used, or the wrong letter.

JavaScript
function exist(board, word) {  const R = board.length, C = board[0].length;  function dfs(r, c, k) {    if (k === word.length) return true;                       // every letter matched    if (r < 0 || c < 0 || r >= R || c >= C || board[r][c] !== word[k]) return false;   // prune    const saved = board[r][c];    board[r][c] = "#";                                        // choose: mark this cell as used    const found = dfs(r + 1, c, k + 1) || dfs(r - 1, c, k + 1) || dfs(r, c + 1, k + 1) || dfs(r, c - 1, k + 1);    board[r][c] = saved;                                      // un-choose: free the cell for other paths    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;}const board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]];console.log(exist(board, "ABCCED")); // trueconsole.log(exist(board, "SEE"));    // trueconsole.log(exist(board, "ABCB"));   // false
Always put back what you changed
The most common backtracking bug is to forget the undo. If you do not put the cell back, a path that failed leaves a hole in the grid, and later paths fail by mistake.

N-Queens: pruning with three Sets

Place n queens (chess pieces) on an n × n board so that no queen attacks another. Queens attack along the same row, column or diagonal. Place one queen in each row. The choice in each row is the column. A queen at (row, c) attacks its column c and two diagonals. One diagonal is the cells with the same row − c. The other diagonal is the cells with the same row + c. Keep three Sets (a Set is a collection that keeps each item once and answers “is this item inside?” very quickly), so the question “is this cell attacked?” takes O(1) time (the same short time every time).

JavaScript
function solveNQueens(n) {  const out = [], queens = [];                    // queens[row] = the column of the queen in that row  const cols = new Set(), diag1 = new Set(), diag2 = new Set();  function go(row) {    if (row === n) {      out.push(queens.map((c) => ".".repeat(c) + "Q" + ".".repeat(n - c - 1)));      return;    }    for (let c = 0; c < n; c++) {      if (cols.has(c) || diag1.has(row - c) || diag2.has(row + c)) continue;   // attacked: prune      cols.add(c); diag1.add(row - c); diag2.add(row + c); queens.push(c);      go(row + 1);      queens.pop(); cols.delete(c); diag1.delete(row - c); diag2.delete(row + c);    }  }  go(0);  return out;}console.log(solveNQueens(4).length);                         // 2console.log(JSON.stringify(solveNQueens(4)[0]));             // [".Q..","...Q","Q...","..Q."]console.log(solveNQueens(8).length);                         // 92

Why pruning matters, and what it costs

Dry run · The effect of pruning
ProblemWithout pruningWith pruning
N-Queens, n = 88⁸ = 16.7 million placements2,057 calls (92 answers)
combination sumevery sequence of numbersstops when the sum is bigger than the target
word searchevery path of any lengthstops at the first letter that does not match
palindrome partitioningall 2ⁿ⁻¹ ways to cutonly cuts that make a palindrome

Pruning does not change the worst-case Big-O (the time in the worst case). It is still exponential, which means the work multiplies by a fixed factor for every extra item. But pruning often makes the real running time many times smaller.

In the worst case, backtracking takes exponential time. That is why these problems have small inputs. Interviewers expect you to say this. They also expect you to point at your pruning rule as the reason your code is fast enough.

Practice questions

For each question, write the five answers (state, complete, choices, prune, undo) as comments before you write the code.

Q1Combination sumMedium

You get different positive integers and a target. Return all different combinations that add up to the target. You may use the same number as many times as you want.

Example 1
Input: candidates = [2, 3, 6, 7], target = 7
Output: [[2, 2, 3], [7]]
Explanation: 2 + 2 + 3 = 7 and 7 = 7. Numbers may be reused.
Example 2
Input: candidates = [2, 3, 5], target = 8
Output: [[2,2,2,2],[2,3,3],[3,5]]
Explanation: Three combinations.
Example 3
Input: candidates = [2], target = 1
Output: []
Explanation: No combination.
Stuck? Open one hint at a time
Hint 1
The state is the path and the amount you still need. It is complete when that amount is exactly 0.
Hint 2
You may use a number again, so make the recursive call with the same index. If you only look forward, [2, 3] and [3, 2] do not both appear.
Hint 3
Sort the numbers, and use break as soon as a number is bigger than what remains.
Show the solution with explanations
Approach 1Backtracking with pruning
The idea

This is the algorithm we traced. Choose a number, make the recursive call with the smaller target, then undo.

JavaScript
function combinationSum(candidates, target) {  candidates = [...candidates].sort((a, b) => a - b);  const out = [], path = [];  function go(start, remaining) {    if (remaining === 0) { out.push([...path]); return; }    for (let i = start; i < candidates.length; i++) {      if (candidates[i] > remaining) break;      path.push(candidates[i]);      go(i, remaining - candidates[i]);      path.pop();    }  }  go(0, target);  return out;}console.log(JSON.stringify(combinationSum([2, 3, 6, 7], 7))); // [[2,2,3],[7]]console.log(JSON.stringify(combinationSum([2, 3, 5], 8)));    // [[2,2,2,2],[2,3,3],[3,5]]console.log(JSON.stringify(combinationSum([2], 1)));          // []
How it works

The number of combinations can grow exponentially, so the worst case cannot be better. Pruning keeps it fast in real use.

Which approach should you use?

(LeetCode 39.)

Q2Combination sum IIMedium

You get numbers that may repeat, and a target. Return all different combinations that add up to the target. You may use each element at most once.

Example 1
Input: candidates = [10, 1, 2, 7, 6, 1, 5], target = 8
Output: [[1,1,6],[1,2,5],[1,7],[2,6]]
Explanation: Each number is used at most once. The two 1s are different elements, but they must not make the same combination twice.
Example 2
Input: candidates = [2, 5, 2, 1, 2], target = 5
Output: [[1,2,2],[5]]
Explanation: Only different combinations.
Stuck? Open one hint at a time
Hint 1
Each element can be used only once, so make the recursive call with i + 1.
Hint 2
The input has repeated values. Sort, and skip a value that is equal to the one before it at the same level (Lesson 33, Subsets II).
Show the solution with explanations
Approach 1Sort, skip duplicates at each level, no reuse
The idea

Use both ideas together: i + 1 in the recursive call, and i > start && same as previous → continue.

JavaScript
function combinationSum2(candidates, target) {  candidates = [...candidates].sort((a, b) => a - b);  const out = [], path = [];  function go(start, remaining) {    if (remaining === 0) { out.push([...path]); return; }    for (let i = start; i < candidates.length; i++) {      if (candidates[i] > remaining) break;      if (i > start && candidates[i] === candidates[i - 1]) continue;      path.push(candidates[i]);      go(i + 1, remaining - candidates[i]);      path.pop();    }  }  go(0, target);  return out;}console.log(JSON.stringify(combinationSum2([10, 1, 2, 7, 6, 1, 5], 8))); // [[1,1,6],[1,2,5],[1,7],[2,6]]console.log(JSON.stringify(combinationSum2([2, 5, 2, 1, 2], 5)));        // [[1,2,2],[5]]
How it works

Without the skip line, you would make [1, 2, 5] twice, once for each 1. Sorting also lets you use the early break.

Which approach should you use?

(LeetCode 40.)

Q3Palindrome partitioningMedium

Split a string so that every piece is a palindrome. Return all the possible ways to split it.

Example 1
Input: s = "aab"
Output: [["a","a","b"],["aa","b"]]
Explanation: Every piece is a palindrome.
Example 2
Input: s = "a"
Output: [["a"]]
Explanation: One piece.
Stuck? Open one hint at a time
Hint 1
At each start position, the choice is where the next piece ends.
Hint 2
Choose only a piece that is a palindrome. When the start reaches the end of the string, save the path.
Show all 2 solutions with explanations
Approach 1Backtrack with a palindrome check
The idea

Try every end position for the current start. Skip pieces that are not palindromes. Make the recursive call from end + 1.

JavaScript
function partition(s) {  const out = [], path = [];  const isPal = (l, r) => {    while (l < r) if (s[l++] !== s[r--]) return false;    return true;  };  function go(start) {    if (start === s.length) { out.push([...path]); return; }    for (let end = start; end < s.length; end++) {      if (!isPal(start, end)) continue;      path.push(s.slice(start, end + 1));      go(end + 1);      path.pop();    }  }  go(0);  return out;}console.log(JSON.stringify(partition("aab"))); // [["a","a","b"],["aa","b"]]console.log(JSON.stringify(partition("a")));   // [["a"]]console.log(partition("aaa").length);          // 4
How it works

The worst case is O(n · 2n). A string of one repeated letter makes every cut valid. The palindrome check costs O(n) for each piece.

Approach 2Work out the palindromes first
The idea

Build a table pal[i][j] once with dynamic programming (solving small parts first and reusing their answers). Then each check takes O(1).

JavaScript
function partition(s) {  const n = s.length;  const pal = Array.from({ length: n }, () => new Array(n).fill(false));  for (let i = n - 1; i >= 0; i--)    for (let j = i; j < n; j++)      pal[i][j] = s[i] === s[j] && (j - i < 2 || pal[i + 1][j - 1]);   // the two ends match and the inside is a palindrome  const out = [], path = [];  function go(start) {    if (start === n) { out.push([...path]); return; }    for (let end = start; end < n; end++) {      if (!pal[start][end]) continue;      path.push(s.slice(start, end + 1));      go(end + 1);      path.pop();    }  }  go(0);  return out;}console.log(JSON.stringify(partition("aab"))); // [["a","a","b"],["aa","b"]]console.log(partition("aaaa").length);         // 8
How it works

The table costs O(n²) to build. After that, every check is O(1). This is your first look at dynamic programming.

Which approach should you use?

Start with the first one. Then mention the table as a way to make it faster. (LeetCode 131.)

Q4Word searchMedium

You get a grid of letters and a word. Return true if the word can be spelled with cells that touch each other (left, right, up or down). You may use 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
Explanation: A → B → C → C → E → D along the grid.
Example 2
Input: same board, word = "SEE"
Output: true
Explanation: S → E → E.
Example 3
Input: same board, word = "ABCB"
Output: false
Explanation: The B would have to be reused.
Stuck? Open one hint at a time
Hint 1
Start a search from every cell. From a cell, try to match the next letter going up, down, left and right.
Hint 2
One path cannot use a cell twice. Mark the cell as used, and put it back when the search leaves the cell.
Hint 3
Stop a path at once when it goes outside the grid, reaches a used cell, or finds a wrong letter.
Show all 2 solutions with explanations
Approach 1Backtracking with marking inside the board
The idea

While a cell is on the current path, write a placeholder in it. Put the letter back afterwards.

JavaScript
function exist(board, word) {  const R = board.length, C = board[0].length;  function dfs(r, c, k) {    if (k === word.length) return true;    if (r < 0 || c < 0 || r >= R || c >= C || board[r][c] !== word[k]) return false;    const saved = board[r][c];    board[r][c] = "#";    const found = dfs(r + 1, c, k + 1) || dfs(r - 1, c, k + 1) || dfs(r, c + 1, k + 1) || dfs(r, c - 1, k + 1);    board[r][c] = saved;    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;}const board = [["A", "B", "C", "E"], ["S", "F", "C", "S"], ["A", "D", "E", "E"]];console.log(exist(board, "ABCCED")); // trueconsole.log(exist(board, "SEE"));    // trueconsole.log(exist(board, "ABCB"));   // false
How it works

The time is O(R · C · 3L) for a word of length L (three directions after the first step). The stack space is O(L). The || chain stops at the first success. Each cell is put back before the function returns, so the board is not left changed.

Approach 2A visited grid instead of changing the board
The idea

If you must not change the input, keep a separate grid of true/false values.

JavaScript
function exist(board, word) {  const R = board.length, C = board[0].length;  const seen = Array.from({ length: R }, () => new Array(C).fill(false));  function dfs(r, c, k) {    if (k === word.length) return true;    if (r < 0 || c < 0 || r >= R || c >= C || seen[r][c] || board[r][c] !== word[k]) return false;    seen[r][c] = true;    const found = dfs(r + 1, c, k + 1) || dfs(r - 1, c, k + 1) || dfs(r, c + 1, k + 1) || dfs(r, c - 1, k + 1);    seen[r][c] = false;    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;}console.log(exist([["a", "b"], ["c", "d"]], "abdc")); // trueconsole.log(exist([["a", "b"], ["c", "d"]], "abcd")); // false
How it works

It is the same search, with O(R · C) extra memory for the visited grid.

Which approach should you use?

Marking inside the board is shorter. Mention the visited grid when the interviewer says “don't change the input”. (LeetCode 79.)

Q5N-QueensHard

Place n queens on an n × n board so that no two queens attack each other. Return every different solution as a list of board rows.

Example 1
Input: n = 4
Output: [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]
Explanation: There are two ways to place 4 queens so that none attacks another.
Example 2
Input: n = 1
Output: [["Q"]]
Explanation: A single queen.
Stuck? Open one hint at a time
Hint 1
Put one queen in each row. The choice in each row is the column.
Hint 2
A queen attacks its column and both diagonals. Which number stays the same along each diagonal?
Hint 3
Along one diagonal, row − col stays the same. Along the other diagonal, row + col stays the same.
Show the solution with explanations
Approach 1Backtracking with three Sets
The idea

Go row by row. Try each column that is not in cols, diag1 (row − col) or diag2 (row + col).

JavaScript
function solveNQueens(n) {  const out = [], queens = [];  const cols = new Set(), diag1 = new Set(), diag2 = new Set();  function go(row) {    if (row === n) {      out.push(queens.map((c) => ".".repeat(c) + "Q" + ".".repeat(n - c - 1)));      return;    }    for (let c = 0; c < n; c++) {      if (cols.has(c) || diag1.has(row - c) || diag2.has(row + c)) continue;      cols.add(c); diag1.add(row - c); diag2.add(row + c); queens.push(c);      go(row + 1);      queens.pop(); cols.delete(c); diag1.delete(row - c); diag2.delete(row + c);    }  }  go(0);  return out;}console.log(JSON.stringify(solveNQueens(4)));  // [[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]console.log(JSON.stringify(solveNQueens(1)));  // [["Q"]]console.log(solveNQueens(6).length);           // 4console.log(solveNQueens(8).length);           // 92
How it works

For n = 8 the search makes 2,057 calls. It does not check all 88 placements. The worst case is still exponential, but the Sets make the attack check O(1).

Which approach should you use?

(LeetCode 51. LeetCode's N-Queens II is the same problem, but it only counts the solutions.)

Q6Combination sum IIIMedium

Find all combinations of k different numbers from 1 to 9 that add up to n.

Example 1
Input: k = 3, n = 7
Output: [[1, 2, 4]]
Explanation: Three different digits from 1 to 9 that add up to 7.
Example 2
Input: k = 3, n = 9
Output: [[1,2,6],[1,3,5],[2,3,4]]
Explanation: Three combinations.
Example 3
Input: k = 4, n = 1
Output: []
Explanation: Four digits cannot sum to 1.
Stuck? Open one hint at a time
Hint 1
The numbers you can use are fixed: 1 to 9, each used at most once.
Hint 2
The path is complete when it has k numbers. It is an answer if the sum is n. Prune when the sum is already bigger than n.
Show the solution with explanations
Approach 1Backtracking over 1–9
The idea

Loop from start to 9 and make the recursive call with i + 1. Stop early when the number is bigger than the sum that remains.

JavaScript
function combinationSum3(k, n) {  const out = [], path = [];  function go(start, remaining) {    if (path.length === k) {      if (remaining === 0) out.push([...path]);      return;    }    for (let i = start; i <= 9; i++) {      if (i > remaining) break;                   // prune: this number alone is already too big      path.push(i);      go(i + 1, remaining - i);      path.pop();    }  }  go(1, n);  return out;}console.log(JSON.stringify(combinationSum3(3, 7))); // [[1,2,4]]console.log(JSON.stringify(combinationSum3(3, 9))); // [[1,2,6],[1,3,5],[2,3,4]]console.log(JSON.stringify(combinationSum3(4, 1))); // []
How it works

There are at most C(9, k) combinations, so the search is very small. The point is to use the same template with slightly different rules.

Which approach should you use?

(LeetCode 216.)

Q7Restore IP addressesMedium

You get a string of digits. Return every valid IPv4 address (four numbers separated by dots) that you can make by adding three dots. You cannot change the order of the digits or remove any digit.

Example 1
Input: s = "25525511135"
Output: ["255.255.11.135","255.255.111.35"]
Explanation: Four parts. Each part is from 0 to 255 and has no zero at the front.
Example 2
Input: s = "0000"
Output: ["0.0.0.0"]
Explanation: A part can be 0, but it cannot be 00.
Example 3
Input: s = "101023"
Output: 5 addresses
Explanation: There are several ways to cut six digits into four parts.
Stuck? Open one hint at a time
Hint 1
There are four parts. Each part has 1 to 3 digits. At each step, the choice is how long the part is.
Hint 2
Prune a part that starts with a zero (unless it is just “0”) or has a value above 255.
Hint 3
It is an answer only if exactly four parts use the whole string.
Show the solution with explanations
Approach 1Backtrack on part lengths
The idea

Choose a length of 1 to 3 and check that the piece is valid. Then make the recursive call for the next part. Save the answer when four parts use the whole string.

JavaScript
function restoreIpAddresses(s) {  const out = [], parts = [];  function go(start) {    if (parts.length === 4) {      if (start === s.length) out.push(parts.join("."));      return;    }    for (let len = 1; len <= 3 && start + len <= s.length; len++) {      const seg = s.slice(start, start + len);      if (seg.length > 1 && seg[0] === "0") break;     // no zero at the front      if (Number(seg) > 255) break;                    // too big (longer pieces are even bigger)      parts.push(seg);      go(start + len);      parts.pop();    }  }  go(0);  return out;}console.log(JSON.stringify(restoreIpAddresses("25525511135"))); // ["255.255.11.135","255.255.111.35"]console.log(JSON.stringify(restoreIpAddresses("0000")));        // ["0.0.0.0"]console.log(JSON.stringify(restoreIpAddresses("101023")));      // ["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
How it works

The search tree has at most 3 choices at each of 4 levels, so at most 81 leaves. The running time is effectively constant, O(1), for any input length that can make an address.

Which approach should you use?

(LeetCode 93.) Here the tree is small. The hard part is to write the validity checks correctly.

Dry run · State, choices and pruning for each problem
ProblemChoice at each stepPrune when…Save when…
combination sumwhich number (may be used again)number > remainingremaining = 0
combination sum IIwhich number (once, skip repeated values)number > remainingremaining = 0
palindrome partitioningend of the next piecepiece is not a palindromestart = length
word searchone of 4 neighboursout of bounds / used / wrong letterall letters matched
N-Queenscolumn in this rowcolumn or diagonal attackedrow = n
restore IPpart length 1–3leading zero or > 2554 parts use all digits

Make it stick

Make it stick — close this page, then
  1. Write the backtracking template from memory and point at the pruning line.
  2. Explain why combination sum recurses with i but combination sum II recurses with i + 1.
  3. Explain how the three Sets in N-Queens save you from scanning the board.
  4. Explain what goes wrong if you forget to put a cell back in word search.

Revisit schedule: solve two of the questions again tomorrow, again in 3 days, and once more in a week — without looking at the answers. Each time it will feel easier. That is the memory forming.

Part 8 complete: what's next

You can now explore decision trees, with rules and without rules. Part 9 uses a new data structure: linked lists. In a linked list, every element points to the next one. The main skill is to change the pointers instead of moving items around in an array.

Practise on LeetCode

Real interview problems that use exactly what this lesson teaches. Solve them in JavaScript after the practice questions above.

Published by Jainik · Last updated · How these lessons are made

Keep learning

Part of the study guide

Related series