Backtracking LeetCode Pattern Guide — Permutations, Combinations, and Subsets

A Backtracking LeetCode pattern guide is really a guide to controlled search. Permutations, combinations, and subsets all ask you to build partial answers, explore choices, and undo those choices when a path is complete or impossible. Once you see the pattern, many problems stop feeling like separate puzzles and start looking like variations of the same recursive decision tree.

Backtracking LeetCode pattern guide: the core mental model

Backtracking is depth-first search over possible decisions. At each step, you maintain a partial candidate, choose the next option, recurse, and then remove that option before trying the next one. The classic phrase is "choose, explore, unchoose." That sounds simple, but interview mistakes usually come from choosing the wrong state, failing to copy the path, or not handling duplicates.

A minimal template looks like this in words:

1. Keep a path that represents the partial answer.
2. If the path satisfies the goal, copy it into the result.
3. Loop over candidate choices.
4. Skip invalid or duplicate choices.
5. Add the choice to the path.
6. Recurse with updated state.
7. Remove the choice so the next branch starts cleanly.

The important part is not the syntax. It is identifying the state. For permutations, state usually includes a used set. For combinations and subsets, state usually includes a start index. For constraint problems like N-Queens or Sudoku, state includes occupied columns, diagonals, rows, boxes, or other validity checks.

The decision table: permutation, combination, or subset?

Use the problem wording to decide the shape of the recursion.

| Problem type | Order matters? | Can reuse elements? | Typical state | Example | |---|---|---|---|---| | Permutations | Yes | Usually no | path + used set | Arrange all numbers | | Combinations | No | Sometimes yes | path + start index | Choose k numbers | | Subsets | No | No | path + start index | All possible subsets | | Combination sum | No | Often yes | path + start index + remaining target | Sum to target | | Partitioning | Sequence order fixed | Cut positions vary | start index + path of pieces | Palindrome partitioning | | Constraint grid | Depends | Depends | board + validity sets | N-Queens, Sudoku |

A quick rule: if choosing [1,2] and [2,1] should count as different, you need permutation logic. If they are the same answer, use a start index to prevent reordering duplicates. If every element can be included or excluded, subsets logic works.

Permutations: use a used set, not a start index

In a permutation problem, each position in the answer can use any unused element. The recursion depth usually equals the length of the final arrangement. You stop when len(path) == len(nums) and add a copy of the path.

The common mistake is passing start + 1 like a combination problem. That prevents later positions from using earlier unused elements and misses valid arrangements. Instead, loop over every index each time and skip indices already in the path.

For nums = [1,2,3], the tree starts with three choices: 1, 2, or 3. If you choose 1, the next choices are 2 or 3. If you choose 2 after 1, the next choice is 3, producing [1,2,3]. Then you remove 3, remove 2, choose 3, and continue. That remove step is not housekeeping; it is what allows the sibling branch to be correct.

If duplicates exist, sort first and skip a duplicate when the previous equal value has not been used in the current branch. The intuition: among identical values, only the first unused copy should start a branch at a given depth. Without that rule, [1a,1b,2] and [1b,1a,2] appear as duplicate outputs.

Interview talk track: "Because order matters, I will not use a monotonically increasing start index. I will track which indices are already used, build the permutation position by position, and copy the path when it reaches the input length. If duplicates are allowed, I will sort and skip duplicate choices at the same depth."

Combinations: use a start index to prevent reordering

Combination problems ask for groups, not arrangements. [1,2,3] is the same group no matter the order. That means once you choose an element at index i, the next recursion should start at i + 1 if elements cannot be reused. This keeps the path in a consistent order and prevents duplicates.

For "choose k numbers from 1 to n," the state is start, path, and maybe k. Stop when len(path) == k. The loop runs from start to n. Choose the current number, recurse from the next number, then remove it.

Pruning matters here. If you need 3 more numbers and only 2 remain, there is no reason to continue. In code, you can limit the loop so there are enough remaining elements to complete the combination. In interviews, say the pruning out loud: "I can stop early when the remaining candidates cannot fill the path."

For combination sum variants, pay attention to reuse. If the same number can be reused, recurse with the same index i. If each number can be used once, recurse with i + 1. If the input has duplicates, sort and skip equal values at the same recursion depth.

Subsets: include/exclude or loop-based expansion

Subsets are all possible selections. There are two clean approaches.

The include/exclude approach makes a binary decision for each element: take it or skip it. It is intuitive and produces a recursion tree of size 2^n. The loop-based approach adds the current path to results at every depth, then loops from start onward choosing the next element. Both are valid.

Loop-based subset template in words:

• Add a copy of the current path to results immediately.
• For each index from start to the end:
• Skip duplicates at the same depth if needed.
• Choose nums[i].
• Recurse with i + 1.
• Remove nums[i].

Why add the path before the loop? Because every partial path is itself a subset. The empty path represents the empty subset. After choosing 1, [1] is a subset, and deeper branches create [1,2], [1,2,3], and so on.

For duplicate subsets, sort first and skip when i > start and nums[i] == nums[i-1]. The i > start part is crucial. It means "skip duplicates among sibling choices," not "skip all duplicate values everywhere." If you skip too aggressively, you lose valid subsets like [2,2].

Constraint backtracking: validity checks are the performance lever

Problems like N-Queens, Sudoku Solver, Word Search, and Restore IP Addresses add constraints. The same backtracking skeleton remains, but a fast validity check determines whether the solution is usable.

For N-Queens, place one queen per row. The state includes occupied columns, positive diagonals, and negative diagonals. A square is valid if its column and both diagonals are unused. Instead of scanning the whole board each time, maintain sets. That turns validity checks from board scans into constant-time lookups.

For Sudoku, track used digits per row, column, and 3x3 box. Pick the next empty cell, try digits 1-9, and backtrack when a digit violates a constraint. A smart improvement is choosing the empty cell with the fewest candidates first, which reduces branching.

For Word Search, the path is a sequence of grid cells. You mark a cell visited, explore neighbors, then unmark it. The trap is using one global visited set across all starting cells without clearing it. Visited state belongs to the current path, not the whole search.

Pruning: when to stop exploring early

Backtracking can be exponential, so pruning is not optional for harder problems. Good pruning comes from problem constraints.

Examples:

• In combination sum, stop when the remaining target is negative.
• If candidates are sorted and the current candidate exceeds the remaining target, break the loop rather than continue.
• In palindrome partitioning, only recurse on cuts where the substring is a palindrome.
• In IP address restoration, stop if a segment has leading zeros or exceeds 255.
• In k-combination problems, stop when not enough elements remain.
• In N-Queens, skip columns and diagonals that are already attacked.

Pruning should preserve correctness. Do not prune just because a branch "looks unlikely" unless you can prove it cannot lead to a solution.

Common backtracking traps

Forgetting to copy the path: If you append the path object itself to results, later modifications change every stored answer. Copy it when recording a result.

Using the wrong index rule: Permutations need a used set. Combinations and subsets usually need a start index. Mixing these creates missing or duplicate answers.

Skipping duplicates incorrectly: Sort first, then skip duplicates at the same recursion depth. The condition differs between permutations and combinations.

Not undoing state: If you add to a set, mark a board cell, or append to a path, undo it before the next sibling branch.

Bad base case: A base case should match the required output. For subsets, every path is output. For permutations, only full-length paths are output. For combination sum, output only when remaining target is zero.

Ignoring complexity: Many backtracking solutions are exponential. Say so. For permutations, output size alone is n!. For subsets, it is 2^n. You cannot do better than output size.

Interview explanation template

When you see a backtracking problem, explain it like this:

"I will model this as a DFS over partial candidates. The path holds the current candidate. At each step I choose from valid remaining options, recurse, then undo the choice. The base case is when the path satisfies the output condition. To avoid duplicates, I will sort and skip repeated sibling choices. The complexity is proportional to the number of valid candidates generated, which is exponential in the worst case."

Then tailor the details. For permutations, say used set. For combinations, say start index. For constraints, say validity sets and pruning.

Practice order for backtracking prep

Do these in sequence:

1. Subsets
2. Subsets II
3. Combinations
4. Combination Sum
5. Combination Sum II
6. Permutations
7. Permutations II
8. Palindrome Partitioning
9. Word Search
10. N-Queens
11. Sudoku Solver

After each problem, write down the state variables and the duplicate rule. The pattern will become much clearer than if you randomly grind thirty problems.

Backtracking interviews reward disciplined recursion. You do not need magic insight for every prompt. You need to identify the candidate path, choose the right state, prune safely, copy outputs, and explain why your duplicate handling is correct. Once those pieces are automatic, permutations, combinations, subsets, and constraint searches become variations you can solve under pressure.

Related guides

• BFS LeetCode Pattern Guide — Shortest-Path, Level-Order, and Multi-Source — A BFS LeetCode pattern guide for recognizing queue-based problems, implementing level-order traversal, solving unweighted shortest paths, using multi-source BFS, and avoiding common visited-state bugs.
• Binary Search LeetCode Pattern Guide — Bounds, Rotated Arrays, and Search-on-Answer — A binary search LeetCode pattern guide for exact search, lower/upper bounds, rotated arrays, and search-on-answer problems. Includes invariants, templates, traps, and interview-ready explanations.
• Bit Manipulation LeetCode Pattern Guide — XOR Tricks, Masks, and Counting Bits — A practical bit manipulation LeetCode pattern guide covering XOR tricks, masks, counting bits, subset enumeration, flags, and the interview pitfalls around signed integers.
• DFS LeetCode Pattern Guide — Recursion Templates and Grid/Graph Problems — A DFS LeetCode pattern guide with recursion templates, visited-set rules, grid and graph examples, backtracking structure, complexity notes, and interview pitfalls.
• Divide and Conquer LeetCode Pattern Guide — Merge Sort, Quickselect, and Recursion — A practical LeetCode pattern guide for divide and conquer: master recursive contracts, merge sort variations, quickselect, tree recursion, complexity, and common interview traps.