Get started

Backtracking Coding Problems: 18 Questions with Solutions

18 backtracking coding problems — 2 easy · 15 medium · 1 hard — with solutions in 13 languages. Plus a step-by-step walkthrough and a 6-day plan.

  • Problems: 18
  • By difficulty: 2 easy · 15 medium · 1 hard
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
  • Cost: Free on every plan; sign in to run and submit

Backtracking builds a solution one choice at a time and undoes the last choice the moment it cannot lead anywhere. Permutations, subsets, combinations that sum to a target, N-Queens and word search are its standard problems; the skill is in the ordering of choices and the pruning that keeps the search from visiting what a rule already forbids.

How backtracking works, step by step

+1+2+3+3+4+4+2+3+4+3+4+40136485256374sumpath: [4] · sum: 4, dead endfound: [1, 4], [2, 3]
Subsets that sum to a target, with backtracking. Example: nums = [1, 2, 3, 4], target = 5
  1. Find every subset of [1, 2, 3, 4] that sums to 5. Backtracking builds a subset one choice at a time (each node shows its sum, each edge the number added): pick a larger number, recurse, undo, try the next, and abandon a branch once its sum passes 5.
  2. Choose 1: the path is [1] with sum 1, still below 5, so the search goes deeper with the numbers after 1.
  3. Choose 2: the path is [1, 2] with sum 3, still below 5, so the search goes deeper with the numbers after 2.
  4. Try 3: the sum would be 6, more than 5, so the branch is cut without going in. The numbers are sorted, so 4 would overshoot too and is skipped as well.
  5. Undo 2, then choose 3: the path is [1, 3] with sum 4, still below 5, so the search goes deeper with the numbers after 3.
  6. Try 4: the sum would be 8, more than 5, so the branch is cut without going in. The numbers are sorted, so there is nothing larger left to try.
  7. Undo 3, then choose 4: [1, 4] sums to exactly 5, so it is recorded as an answer. Adding anything more would overshoot, so the search backs up from here.
  8. Undo 4 and 1, then choose 2: the path is [2] with sum 2, still below 5, so the search goes deeper with the numbers after 2.
  9. Choose 3: [2, 3] sums to exactly 5, so it is recorded as an answer. Adding anything more would overshoot, so the search backs up from here.
  10. Undo 3, then try 4: the sum would be 6, more than 5, so the branch is cut without going in. The numbers are sorted, so there is nothing larger left to try.
  11. Undo 2, then choose 3: the path is [3] with sum 3, still below 5, so the search goes deeper with the numbers after 3.
  12. Try 4: the sum would be 7, more than 5, so the branch is cut without going in. The numbers are sorted, so there is nothing larger left to try.
  13. Undo 3, then choose 4: the sum is 4, but no larger number is left, so the branch ends without an answer. The search is done: [1, 4] and [2, 3] sum to 5. Pruning cut 4 branches early; the worst case is still O(2^n) subsets.

Backtracking study plan

10 of the 18 Backtracking problems (2 easy, 7 medium and 1 hard) over 6 days, about 5 h 50 min in all — the pattern first, then easiest to hardest. After that, the other 8 in the full list below are practice at your own pace. Then move on to Graph.

Day 1

Learn the pattern: read the essentials and step through the walkthrough above, then solve these 2.

Day 2

Medium problems: the same pattern with one twist each. Name the twist before you code.

Day 3

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 4

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 5

More mediums. Before coding each one, write down what state the pattern keeps and when it changes.

Day 6

Hard problems: the pattern combined with a second idea. Give each a full attempt before reading the editorial.

Next topic: Graph

Backtracking: the essentials

When to reach for it

"Return all" — every permutation, subset, combination, partition, placement or path — or "does any arrangement exist" when no polynomial structure is in sight. Small limits give it away: n up to about 10–20, a 9 × 9 board, a word of length 15. If the question wants only how many, or the best one, first check whether Dynamic Programming can count them without listing them.

The pattern

A recursive function holds a partial solution. At each level, loop over the choices still allowed; for each, apply it, recurse, then undo it exactly. Record a copy whenever the partial solution is complete. Prune a branch the moment it cannot succeed — a running sum already past the target, a square already attacked.

def subsets(nums):
    out, path = [], []
    def go(start):
        out.append(path[:])         # a copy, not the live list
        for i in range(start, len(nums)):
            path.append(nums[i])
            go(i + 1)
            path.pop()              # undo
    go(0)
    return out

Cost

Proportional to the nodes in the search tree: O(2ⁿ × n) for subsets and O(n! × n) for permutations, the factor n being the copy of each answer. Pruning cuts the constant, rarely the bound.

Common mistakes

  • Appending the live path instead of a copy, so every recorded answer ends up empty.
  • Forgetting to undo a choice, or a visited mark on a board, which leaks into sibling branches.
  • Duplicate answers from duplicate inputs: sort first, then skip nums[i] == nums[i - 1] when i > start.
  • Recursing with i + 1 where an item may be reused; Combination Sum recurses with i.

Start with

All backtracking problems

Easy (2)

Medium (15)

Hard (1)

Companies that ask backtracking problems

  • Amazon 11 problems on backtracking
  • Google 9 problems on backtracking
  • Microsoft 4 problems on backtracking
  • Adobe 3 problems on backtracking
  • Meta 2 problems on backtracking
  • Bloomberg 1 problem on backtracking
  • Intuit 1 problem on backtracking
  • Oracle 1 problem on backtracking
  • Samsung 1 problem on backtracking

Next topic: Graph