Backtracking Pattern: How to Generate Combinations Without Losing Your Mind

Backtracking is the pattern you use when a problem asks you to generate, explore, or validate many possible choices. It is less about clever math and more about disciplined search.

The structure is always the same:

1. choose an option
2. explore deeper
3. undo the choice

Once you see that rhythm, a huge family of recursion problems becomes much easier.

When to Reach for Backtracking

Backtracking is a strong fit when the problem asks for:

• all subsets
• all permutations
• all combinations
• valid configurations such as N-Queens or Sudoku
• a path that satisfies constraints

These problems usually involve a decision tree where each level adds one more choice.

Template

def backtrack(path, choices):
    if is_complete(path):
        results.append(path.copy())
        return

    for choice in choices:
        if not is_valid(choice, path):
            continue

        path.append(choice)
        backtrack(path, updated_choices)
        path.pop()

The two key details are:

• append before the recursive call
• pop immediately after it

That pop() is what restores the state for the next branch.

Example: Generate All Subsets

def subsets(nums: list[int]) -> list[list[int]]:
    result: list[list[int]] = []
    path: list[int] = []

    def dfs(index: int) -> None:
        result.append(path.copy())

        for i in range(index, len(nums)):
            path.append(nums[i])
            dfs(i + 1)
            path.pop()

    dfs(0)
    return result

At each step, we decide which next element to include. Because we advance the start index, we avoid duplicates and preserve combination order.

Example: Generate All Permutations

Permutations require a different state rule because position matters.

def permute(nums: list[int]) -> list[list[int]]:
    result: list[list[int]] = []
    path: list[int] = []
    used = [False] * len(nums)

    def dfs() -> None:
        if len(path) == len(nums):
            result.append(path.copy())
            return

        for i in range(len(nums)):
            if used[i]:
                continue

            used[i] = True
            path.append(nums[i])
            dfs()
            path.pop()
            used[i] = False

    dfs()
    return result

The used array tracks which elements are already in the current permutation.

Pruning

Good backtracking is not just brute force. The real win comes from pruning, which means stopping branches that can never lead to a valid answer.

Examples:

• current sum already exceeds target
• partial board placement is invalid
• remaining characters cannot form a valid partition

Pruning is what turns backtracking from acceptable to excellent.

Common Mistakes

• Forgetting to undo state changes
• Reusing the same mutable list without copying when saving answers
• Exploring branches that are already impossible
• Confusing permutations with combinations

If your output contains repeated or corrupted paths, it is usually a state-restoration issue.

Complexity

Backtracking is often exponential because it explores many branches. That is normal. The goal is not always to make it polynomial. The goal is to search clearly and prune aggressively.

Practice These Next

• Subsets
• Combination Sum
• Permutations
• Palindrome Partitioning
• N-Queens

Backtracking gets much easier once you stop thinking of each problem as unique and start seeing the same search skeleton underneath.