Backtracking Explained: N-Queens to Subsets

If dynamic programming is the interview topic people fear most, backtracking is the one they fumble most. It shows up constantly — subsets, permutations, combination sum, word search, N-Queens — and candidates who haven’t internalized the pattern end up improvising recursion under pressure, which rarely goes well.

Here’s the good news: almost every backtracking interview problem is the same problem wearing a different costume. Once you learn the template, you stop memorizing solutions and start generating them. This post walks through the template and applies it to the four problem types that cover the vast majority of backtracking questions you’ll actually be asked.

What Is Backtracking, Really?

Backtracking is depth-first search over a decision tree, with one extra move: when a path can’t lead to a valid answer, you undo your last decision and try something else.

Think of solving a maze. At each junction you pick a direction, walk, and if you hit a dead end, you walk back to the junction and try the next direction. You don’t restart the maze from the entrance — you undo only the last choice. That “undo” is the backtrack.

Every backtracking problem has three ingredients:

1. Choices — at each step, what options do I have? (Which number to place next? Include this element or not?)
2. Constraints — which choices are invalid? (Queens can’t share a diagonal; digits can’t repeat in a Sudoku row.)
3. Goal — when is a partial solution complete? (The path has length n; we’ve placed all queens; the sum equals the target.)

If you can answer those three questions for a problem, you can solve it with backtracking. If you can’t, it’s probably not a backtracking problem.

How Do You Recognize a Backtracking Problem?

Watch for these phrases in the problem statement:

• “Return all possible…” (all subsets, all permutations, all paths)
• “Find all combinations that sum to…”
• “Generate all valid…” (parentheses, IP addresses, board configurations)
• “Place N things so that no two conflict”

The keyword is all. Problems asking for the count or the best solution often have dynamic programming answers, but problems asking you to enumerate solutions almost always want backtracking. (For counting problems, start with Day 30: Dynamic Programming Introduction instead.)

The Template: Choose, Explore, Unchoose

Here is the skeleton that solves everything in this post:

 1def backtrack(state, choices, result):
 2    if is_goal(state):
 3        result.append(state.copy())  # record a snapshot
 4        return
 5
 6    for choice in choices:
 7        if not is_valid(choice, state):
 8            continue           # prune invalid branches
 9
10        state.append(choice)   # 1. CHOOSE
11        backtrack(state, next_choices, result)  # 2. EXPLORE
12        state.pop()            # 3. UNCHOOSE

Three moves, always in this order:

1. Choose — commit to one option by mutating your current state.
2. Explore — recurse to solve the rest of the problem with that choice locked in.
3. Unchoose — undo the mutation so the loop can try the next option from a clean slate.

Two details in the template cause the majority of bugs, so let’s name them now:

• state.copy() at the goal. state is a mutable list that you keep modifying. If you append state itself, every entry in result ends up pointing at the same list — which will be empty by the time the recursion finishes. Always append a copy.
• Symmetry between choose and unchoose. Whatever you mutate before the recursive call, you must un-mutate after it. If you append, you pop. If you mark a cell used, you unmark it. Asymmetry here corrupts state for sibling branches, and the resulting bugs are miserable to trace.

If you want a gentler on-ramp before the interview problems, Day 48: Introduction to Backtracking builds this template from first principles.

Now let’s apply it four times.

Type 1: Subsets (Include/Exclude Decisions)

Problem: Given an array of distinct integers, return all possible subsets (the power set). For [1, 2, 3], return [[], [1], [2], [3], [1,2], [1,3], [2,3], [1,2,3]].

The decision at each element is binary: include it or don’t. A clean way to express that is a loop with a start index, where every partial state along the way is itself a valid subset:

 1def subsets(nums):
 2    result = []
 3
 4    def backtrack(start, current):
 5        result.append(current.copy())  # every node in the tree is a subset
 6
 7        for i in range(start, len(nums)):
 8            current.append(nums[i])        # choose
 9            backtrack(i + 1, current)      # explore (only elements after i)
10            current.pop()                  # unchoose
11
12    backtrack(0, [])
13    return result

The start parameter is doing quiet but important work: by only considering elements at index i + 1 and beyond, we guarantee each subset is generated exactly once, in a canonical order. Without it, you’d generate [1, 2] and [2, 1] as separate results.

Complexity: There are 2^n subsets and copying each costs up to O(n), so the total is O(n · 2^n). That’s exponential — and unavoidable, because the output itself is exponential in size. When your interviewer asks “can we do better?”, the answer is no, and saying so confidently is worth points.

This problem also has a beautiful bit-manipulation solution covered in Day 54: Power Set — mentioning the alternative is a nice flex in an interview.

Type 2: Permutations (Ordering Decisions)

Problem: Given an array of distinct integers, return all possible orderings. For [1, 2, 3], there are 3! = 6 permutations.

Subsets asked “in or out?” Permutations ask “what comes next?” Every element must appear, so the decision at each level is which unused element to place in the next position:

 1def permutations(nums):
 2    result = []
 3    used = set()
 4
 5    def backtrack(current):
 6        if len(current) == len(nums):      # goal: every element placed
 7            result.append(current.copy())
 8            return
 9
10        for num in nums:
11            if num in used:
12                continue                   # constraint: no repeats
13
14            used.add(num)                  # choose
15            current.append(num)
16            backtrack(current)             # explore
17            current.pop()                  # unchoose (both mutations!)
18            used.remove(num)
19
20    backtrack([])
21    return result

Note the symmetry: we mutate two things (the used set and the current list), so we must undo two things. This is where the choose/unchoose discipline earns its keep.

Complexity: n! permutations, each of length n, gives O(n · n!). The used set makes the validity check O(1) — checking num in current (a list scan) would work too, but costs O(n) per check and is the kind of small inefficiency interviewers notice.

Type 3: Combination Sum (Choices With Reuse and Pruning)

Problem: Given distinct candidate numbers and a target, return all unique combinations where the chosen numbers sum to the target. The same number may be used unlimited times. For candidates [2, 3, 6, 7] and target 7: [[2, 2, 3], [7]].

Two twists on the subsets pattern:

1. Reuse is allowed — so when we recurse, we pass i instead of i + 1 (an element may pick itself again).
2. We can prune — once the running sum exceeds the target, no deeper choice can fix it, so we abandon the branch immediately.

 1def combination_sum(candidates, target):
 2    result = []
 3    candidates.sort()  # enables early termination in the loop
 4
 5    def backtrack(start, current, remaining):
 6        if remaining == 0:                 # goal: exact sum reached
 7            result.append(current.copy())
 8            return
 9
10        for i in range(start, len(candidates)):
11            if candidates[i] > remaining:
12                break                      # prune: sorted, so all later ones fail too
13
14            current.append(candidates[i])              # choose
15            backtrack(i, current, remaining - candidates[i])  # explore (i, not i+1: reuse OK)
16            current.pop()                              # unchoose
17
18    backtrack(0, [], target)
19    return result

Sorting first turns the prune from a continue (skip this one) into a break (skip everything after it too), which kills entire subtrees at once. Pruning is the difference between backtracking that passes and backtracking that times out, and interviewers frequently ask about it as a follow-up. Get ahead of them: mention the prune as you write it.

Notice also that start = i (not i + 1) is the only line that changed to allow reuse. Being able to articulate that one-line difference shows you understand the template rather than having memorized two separate solutions.

Type 4: N-Queens (Constraint Satisfaction)

Problem: Place N queens on an N×N chessboard so that no two queens attack each other. Return all distinct board configurations.

This is the classic — the problem backtracking was practically invented for. The key insight that simplifies everything: exactly one queen goes in each row, so we place queens row by row, and the only decision per row is which column.

The constraints are: no shared column, no shared diagonal. Rather than scanning the board to check safety, we track attacked lines in sets, using two facts about diagonals:

• Cells on the same ↘ diagonal share the same row - col.
• Cells on the same ↙ diagonal share the same row + col.

 1def solve_n_queens(n):
 2    result = []
 3    cols, diag1, diag2 = set(), set(), set()
 4    placement = []  # placement[r] = column of the queen in row r
 5
 6    def backtrack(row):
 7        if row == n:                        # goal: all rows filled
 8            board = ["." * c + "Q" + "." * (n - c - 1) for c in placement]
 9            result.append(board)
10            return
11
12        for col in range(n):
13            if col in cols or (row - col) in diag1 or (row + col) in diag2:
14                continue                    # constraint: square is attacked
15
16            cols.add(col)                   # choose
17            diag1.add(row - col)
18            diag2.add(row + col)
19            placement.append(col)
20
21            backtrack(row + 1)              # explore
22
23            cols.remove(col)                # unchoose — mirror every mutation
24            diag1.remove(row - col)
25            diag2.remove(row + col)
26            placement.pop()
27    backtrack(0)
28    return result

Same three moves as the subsets problem — there’s just more state to choose and unchoose. The O(1) set lookups replace an O(n) board scan per placement, which matters: N-Queens’ search tree is brutal enough without paying linear cost at every node. (Sound familiar? Constant-time membership checks are exactly why hash maps and sets dominate interviews.)

Complexity: roughly O(n!) — the first queen has n choices, the next has at most n-1 viable columns, and so on. Pruning via the three sets cuts the real search dramatically below the n^n brute force.

For deeper walkthroughs of this family, see Day 49: The N-Queens Problem and its sibling constraint-satisfaction lessons, Day 50: Sudoku Solver and Day 52: Graph Coloring.

The Four Types, Side by Side

Different costumes, same body: choose, explore, unchoose.

How to Practice This

Reading the template is 20% of the work; the other 80% is writing it until the choose/explore/unchoose rhythm is muscle memory. A sequence that works well:

1. Subsets — the purest form of the pattern.
2. Permutations — adds the used-set and double mutation.
3. Combination Sum — adds reuse and pruning.
4. N-Queens — adds multi-part constraint state.

Each problem adds exactly one new idea to the previous one, which is how the backtracking week of our curriculum (Day 48 through Day 52) is sequenced.

If you’re building an interview prep plan around patterns like this — where each day adds one idea instead of drowning you in a random problem list — that’s exactly what the 60 Days of Algorithms challenge is designed to do. Sign up free and you’ll hit backtracking in week 7 with all the recursion foundations already in place. Wondering how this fits a realistic prep schedule? See how long it actually takes to get a FAANG offer.

Related Articles

• Day 48: Introduction to Backtracking
• Day 49: The N-Queens Problem
• Hash Maps and Sets: The Most Underrated FAANG Topic
• How Long Does It Take to Get a FAANG Offer?

Happy coding, and we’ll see you in the next lesson!