Backtracking

Reach for it when

• Subsets and combinations
• Permutations with or without duplicates
• N-Queens and sudoku solving
• Word search on a grid
• Palindrome partitioning

Reference implementation

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

    def backtrack(start: int) -> None:
        result.append(path[:])          # copy — path is mutated after this
        for i in range(start, len(nums)):
            path.append(nums[i])
            backtrack(i + 1)
            path.pop()                  # un-choose

    backtrack(0)
    return result

Complexity: Exponential by nature — O(2^n) subsets, O(n!) permutations. Pruning is the whole game.

What goes wrong

• Appending `path` instead of `path[:]` — every result ends up empty because they share one list.
• Recursing from `start` instead of `i + 1`, which produces combinations with repetition.
• Not sorting first when de-duplicating, so the `nums[i] == nums[i-1]` skip cannot work.

Practise on

• Subsets
• Permutations II
• Combination Sum
• N-Queens
• Word Search