Goal: Make a choice, explore the consequences, and backtrack to try the other choice.

One shared list for every branch

Rather than building a fresh string for every branch, keep a single shared list. Add a character, go down to the bottom of the tree, and when you come back up, remove that character again.

It is like writing a code in pencil on one slip of paper: you write a digit, try everything that follows, then rub the digit out and try the other one. No new paper for each code.

Shared state: add before the call, remove right after.

Forget the removal: and old choices leak into later branches.

n = 2: every path from the top to the bottom is one string

curr: "0"
result: []

Choose '0' for the first position: append it to curr.

Move 1 of 5

Base case

When the list is as long as n, you have made a choice for every position. Join it into a string, add it to the results and return to the caller, which carries on with the other option.

Every call that reaches full length is one finished answer, so the results list ends with all 2 to the power n strings.

Full length reached: save the finished answer.

Return: go back up to the caller.

In code

curr.append("0")      # choose
explore(curr)
curr.pop()            # undo