Know this before you start: “Choose → explore → un-choose”

Backtracking: choose, explore, un-choose

Build answers one decision at a time: make a choice, recurse for the rest, then undo the choice so the next option starts clean.

The idea

Backtracking tries every way of making a series of choices. At each step: add one option to the current path (choose), recurse to make the remaining choices (explore), then remove it (un-choose) and try the next option.

Undoing is what lets one shared path list serve every branch. When the path is complete, save a copy of it.

See it step by step

All orderings of [1, 2, 3]

choose 1 → choose 2 → choose 3 → save [1, 2, 3]; undo 3, undo 2
choose 3 → choose 2 → save [1, 3, 2]; undo… undo 1
Start with 2, then 3: six orderings in total.

In code (Python)

def permutations(nums):
    result, path, used = [], [], [False] * len(nums)

    def explore():
        if len(path) == len(nums):
            result.append(path[:])          # save a copy
            return
        for i, x in enumerate(nums):
            if used[i]:
                continue
            used[i] = True
            path.append(x)                  # choose
            explore()                       # explore
            path.pop()                      # un-choose
            used[i] = False

    explore()
    return result

print(permutations([1, 2, 3]))
# [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]

Exponential: n! orderings, 2ⁿ subsets. Pruning makes it practical.

When you'll use it

“All subsets / permutations / combinations”, N-Queens, Sudoku, word search.

Common mistakes

Saving path instead of path[:], so every answer is the same list.
Forgetting to undo the choice.