Backtracking is a systematic search: build a solution one choice at a time, and as soon as a partial solution cannot succeed, step back and try the next option. It is depth-first traversal of a decision tree.

The template: choose, explore, undo

Decision tree for subsets of three items: at each level take or skip
Decision tree for subsets of three items: at each level take or skip

Keep one mutable path. At every step:

  1. choose: add an item to path;
  2. explore: recurse on the rest of the problem;
  3. undo: remove the item so that the next choice starts from a clean state.

When path is complete, save a copy (path[:]), because the same list keeps changing afterwards.

Subsets: 2^n leaves

For every item there are two branches: skip or take. A set of n items has 2^n subsets.

python
def subsets(items):
    result, path = [], []

    def explore(i):
        if i == len(items):
            result.append(path[:])
            return
        explore(i + 1)           # branch 1: skip items[i]
        path.append(items[i])    # choose
        explore(i + 1)           # branch 2: take items[i]
        path.pop()               # undo

    explore(0)
    return result