The backtracking template

Backtracking is a way to search through all possible solutions by making decisions one at a time. At each step you pick one option, go deeper, and when that path is finished or proves useless you undo the choice and try the next option.

You can picture it as a depth-first walk over a tree of decisions. The root is the empty solution, each edge is one choice, and each leaf is a complete candidate. The key habit is choose, explore, un-choose: the shared state (a path list, a used set, a board) is modified before the recursive call and restored right after it.

Backtracking is the go-to technique when a problem says generate all, list every, find any arrangement, or count the ways, and the input is small (often n up to about 10 to 20).

1. 1Define the state: what partial solution you are building (for example a list called path) and any helpers (a used array, counters, sets of blocked cells).
2. 2Define the goal check: when is the partial solution complete? If complete, record a copy of it (path[:]) and return.
3. 3Define the choices available from this state, for example the numbers not used yet, or the two characters ( and ).
4. 4For each choice that is still valid: apply it to the state (choose), recurse (explore), then reverse exactly what you applied (un-choose).
5. 5Skip choices that can never lead to a valid answer. This is pruning, and it is what turns a brute force into a fast search.
6. 6The running time is roughly the number of nodes in the decision tree times the work per node, which is why answers are usually written as O(2^n) or O(n!) times the cost of copying a result.

def generate_parentheses(n):
    result, path = [], []

    def backtrack(open_count, close_count):
        if len(path) == 2 * n:              # goal: a full string
            result.append("".join(path))    # record a copy
            return
        if open_count < n:                  # choice 1: add "("
            path.append("(")
            backtrack(open_count + 1, close_count)
            path.pop()                      # undo
        if close_count < open_count:        # choice 2: add ")"
            path.append(")")
            backtrack(open_count, close_count + 1)
            path.pop()                      # undo

    backtrack(0, 0)
    return result

print(generate_parentheses(2))  # ['(())', '()()']

The path list is shared by every call. Each choice is appended before the recursive call and popped right after, so when control returns to a caller the path is exactly as it was. The two if checks prune invalid strings instead of generating all 2^(2n) strings and filtering. The number of results is the n-th Catalan number (5 for n = 3).

Cost: Time is the number of nodes in the decision tree times the work per node, typically O(2^n * n) or O(n! * n). Extra space is O(n) for the recursion depth and path, plus the output.