Build a candidate solution step-by-step; abandon (“backtrack”) a branch whenever a partial solution cannot lead to a valid answer.

Data Flow

generate subsets of [1, 2, 3]

                      []
            +--------+--------+
          [1]                []
       +---+---+         +---+---+
     [1,2]  [1]         [2]    []
    +--+--+   |        +--+--+  |
[1,2,3][1,2][1,3][1] [2,3][2]  [3]

When to use

• “Find ALL … combinations / permutations / subsets / paths”.
• Constraint satisfaction (Sudoku, N-Queens, Word Search).

Code (subsets)

def subsets(nums):
    res, path = [], []
    def dfs(i):
        if i == len(nums):
            res.append(path[:])
            return
        path.append(nums[i]); dfs(i+1); path.pop()       # include
        dfs(i+1)                                          # skip
    dfs(0)
    return res

Pitfalls

• Forgetting to undo the choice (path.pop(), remove from constraints) on the way back up.
• No clear base case for “solution complete”.

Analogy

Trying every path in a maze: at every junction drop a marker, try each turn; if you hit a dead end, walk back and pick up the marker.

Interview tip: Three words: choose, explore, un-choose. If you skip un-choose, all subsequent branches see leftover state.