Classic Backtracking Problems

Jr Codex DSA Notes

Level: Intermediate Prerequisites: Chapter 4 Time to complete: ~30 minutes

Table of Contents

1. Subsets
2. Permutations
3. N-Queens
4. Try It Yourself
5. Summary & Next Steps

1. Subsets

Generate every possible subset of a list of unique numbers (including the empty subset and the full list itself). At each element, you have exactly two choices: include it, or don't.

def subsets(nums):
    results = []
 
    def backtrack(start, path):
        results.append(path[:])            # every path is a valid subset — record it
        for i in range(start, len(nums)):
            path.append(nums[i])            # 1. CHOOSE: include nums[i]
            backtrack(i + 1, path)           # 2. EXPLORE: only consider later elements
            path.pop()                        # 3. UNCHOOSE
 
    backtrack(0, [])
    return results
 
print(subsets([1, 2, 3]))
# [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]

path[:] (a copy) is recorded rather than path itself — recording path directly would store a reference to the same list that keeps getting mutated afterward, the same aliasing trap from Python Module 1. Complexity: O(n · 2ⁿ) — 2ⁿ subsets, each up to O(n) to copy.

2. Permutations

Generate every possible ordering of a list of unique numbers. Unlike subsets, every element must appear in every result — the choice is which unused element goes next, not whether to include it at all.

def permutations(nums):
    results = []
 
    def backtrack(path, remaining):
        if not remaining:                    # base case: no elements left to place
            results.append(path[:])
            return
        for i in range(len(remaining)):
            path.append(remaining[i])                          # 1. CHOOSE
            backtrack(path, remaining[:i] + remaining[i+1:])    # 2. EXPLORE
            path.pop()                                            # 3. UNCHOOSE
 
    backtrack([], nums)
    return results
 
print(permutations([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Complexity: O(n · n!) — n! orderings, each O(n) to build. remaining[:i] + remaining[i+1:] also costs O(n) per call to construct; a faster variant swaps elements in place instead of slicing, trading clarity for performance.

3. N-Queens

Place n chess queens on an n×n board so that no two queens attack each other (same row, column, or diagonal). Represent the board as one queen position per row — the choice at each row is which column to place that row's queen in.

def solve_n_queens(n):
    results = []
    columns = set()
    diagonals = set()        # row - col is constant along a "/" diagonal
    anti_diagonals = set()   # row + col is constant along a "\" diagonal
 
    def backtrack(row, placement):
        if row == n:                                 # base case: every row placed
            results.append(placement[:])
            return
 
        for col in range(n):
            if col in columns or (row - col) in diagonals or (row + col) in anti_diagonals:
                continue                                # pruning: skip attacked squares
 
            columns.add(col)                            # 1. CHOOSE
            diagonals.add(row - col)
            anti_diagonals.add(row + col)
            placement.append(col)
 
            backtrack(row + 1, placement)                # 2. EXPLORE
 
            columns.remove(col)                          # 3. UNCHOOSE
            diagonals.remove(row - col)
            anti_diagonals.remove(row + col)
            placement.pop()
 
    backtrack(0, [])
    return results
 
solutions = solve_n_queens(4)
print(len(solutions))   # 2 distinct solutions for a 4x4 board
print(solutions)        # e.g. [[1, 3, 0, 2], [2, 0, 3, 1]] — column per row

The three sets are exactly the pruning (is_valid) logic from Chapter 4's template — checking column/diagonal conflicts in O(1) per candidate, instead of re-scanning previously placed queens, is what keeps this tractable. Without pruning, you'd be generating and checking all n^n placements; with it, invalid branches are cut off immediately.

4. Try It Yourself

Before continuing to Module 5, write a backtracking solution for: given a list of numbers (which may contain duplicates) and a target, find all unique combinations that sum to the target, where each number may be used unlimited times.

def combination_sum(candidates, target):
    # Your solution here — reuse the choose/explore/unchoose template.
    # Hint: the base case is either `remaining == 0` (record the path)
    # or `remaining < 0` (dead end, return without recording).
    pass

def combination_sum(candidates, target):
    results = []
 
    def backtrack(start, remaining, path):
        if remaining == 0:
            results.append(path[:])
            return
        if remaining < 0:
            return
        for i in range(start, len(candidates)):
            path.append(candidates[i])
            backtrack(i, remaining - candidates[i], path)   # `i` not `i+1` — reuse allowed
            path.pop()
 
    backtrack(0, target, [])
    return results
 
print(combination_sum([2, 3, 6, 7], 7))   # [[2, 2, 3], [7]]

5. Summary & Next Steps

Key Takeaways

• Subsets choose "include or skip" for each element; permutations choose "which unused element next"; both follow the same choose/explore/unchoose template from Chapter 4.
• Always record a copy of the working path (path[:]), never the mutable list itself, to avoid the aliasing trap.
• N-Queens shows pruning in action: O(1) conflict checks via sets turn an otherwise intractable brute-force search into something that runs instantly for reasonably sized boards.
• Whether the recursive call passes i or i + 1 (or a modified remaining list) controls whether elements can be reused, skipped, or must be used in order — that one detail is often the entire difference between similar-looking backtracking problems.

Concept Check

1. Why must subsets copy path before appending it to results?
2. What is the choice at each step in Permutations, and how does it differ from the choice in Subsets?
3. In N-Queens, what does each of the three sets (columns, diagonals, anti_diagonals) prevent?

Next Module

→ Module 5: Stacks & Queues

Jr Codex — 1-on-1 Personalized Coaching | Back to Module Index