The include / exclude choice

Packing for a trip, you go through your list of items one by one and decide: take it, or leave it. Every item gets exactly two options. Walking from the first item to the last, and making that choice each time, produces every possible bag, which is all 2 to the power n subsets.

Take the item first, explore what follows, then undo and explore without it.

Include: add the item, then move on to the next one.

Exclude: remove it again, then move on to the next one.

nums = [1, 2]: take it (left) or leave it (right), one number per level

result: []

Level 1 decides about 1. Take it first.

Move 1 of 5

Clone your answer!

The working list keeps changing as the algorithm walks back up the tree. If you save the list itself, every saved answer ends up pointing at the same list, which finishes empty. It is like handing out your only notepad and then erasing it.

You must photocopy the list at the moment you reach the end. The empty subset is always one of the answers.

Save a copy, never the working list itself.

Empty subset: taking nothing is always part of the answer.

In code

res = []
def backtrack(idx, curr):
    if idx == len(nums):
        res.append(list(curr))
        return
    curr.append(nums[idx])
    backtrack(idx + 1, curr)
    curr.pop()
    backtrack(idx + 1, curr)
backtrack(0, [])
return res