Module 16 · Backtracking and Combinatorial Search

151. Generate Binary Strings

Foundation · Download this solution · All solutions and shared helpers

Problem

Return every binary string of length n in lexicographic order, for integer n>=0. Each position contains '0' or '1'. There is one length-zero string, so n=0 returns ['']. The result must contain independent completed strings.

Examples

Example 1

binary_strings(2)
=> ['00', '01', '10', '11']

Each of two positions branches twice.

Example 2

binary_strings(0)
=> ['']

The empty prefix is already complete.

Example 3

binary_strings(1)
=> ['0', '1']

The two single-position choices are emitted in order.

Reveal the worked solution and reasoning

Why this mechanism works

Treat a recursive call as a promise to complete the current prefix. At every unfinished position there are exactly two choices. Append one choice, explore every completion beneath it, then remove that choice before exploring its sibling. This choose-explore-undo structure will become the common protocol for the entire chapter.

State and boundaries

path contains the chosen prefix. Its length is the next position to fill; output contains only complete strings.

Protocol

Start with an empty path.
At length n, join and save the path.
Otherwise append 0 and explore, then undo.
Append 1 and explore, then undo.

Visualization

                 ''
             /        \
           '0'         '1'
          /   \       /   \
        '00' '01'   '10' '11'

Python implementation

def binary_strings(n):
    output, path = [], []
    def visit():
        if len(path) == n:
            output.append(''.join(path))
            return
        for bit in '01':
            path.append(bit)
            visit()
            path.pop()
    visit()
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

binary_strings(2)

L2 binary_strings: output, path = [], []
n=2; output=[]; path=[]

L4 visit: if len(path) == n:
n=2; output=[]; path=[]

L7 visit: for bit in '01':
n=2; output=[]; path=[]; bit='0'

L8 visit: path.append(bit)
n=2; output=[]; path=['0']; bit='0'

L4 visit: if len(path) == n:
n=2; output=[]; path=['0']

L7 visit: for bit in '01':
n=2; output=[]; path=['0']; bit='0'

L8 visit: path.append(bit)
n=2; output=[]; path=['0', '0']; bit='0'

L4 visit: if len(path) == n:
n=2; output=[]; path=['0', '0']

... 25 intermediate state changes omitted ...

L10 visit: path.pop()
n=2; output=['00', '01', '10', '11']; path=['1']; bit='1'

L9 visit: visit()
n=2; output=['00', '01', '10', '11']; path=['1']; bit='1'

L10 visit: path.pop()
n=2; output=['00', '01', '10', '11']; path=[]; bit='1'

L11 binary_strings: visit()
n=2; output=['00', '01', '10', '11']; path=[]

Result: ['00', '01', '10', '11']. Each of two positions branches twice.

binary_strings(0)

L2 binary_strings: output, path = [], []
n=0; output=[]; path=[]

L4 visit: if len(path) == n:
n=0; output=[]; path=[]

L5 visit: output.append(''.join(path))
n=0; output=['']; path=[]

L11 binary_strings: visit()
n=0; output=['']; path=[]

Result: ['']. The empty prefix is already complete.

Why the solution is correct

Every root-to-leaf route makes exactly n binary choices and produces one valid string. Distinct routes differ at some position, so there are no duplicates. Both choices are explored at each position, covering every string; choosing 0 first gives lexical order. Depth increases toward n.

Time and space

O(n*2^n) time and output characters for n>=1; O(n) auxiliary path and recursion depth. At n=0 the work and output are constant.

Common mistakes

Saving the mutable path itself aliases later changes. Forgetting pop leaves a sibling with the previous sibling's choices.

Reasoning card

State: path contains the chosen prefix. Its length is the next position to fill; output contains only complete strings.

Invariant: path contains one choice for every assigned position.

Decision to rehearse: Choose 0/1, recurse, unchoose.

Finish: Append 1 and explore, then undo

Transfer exercise

Forbid adjacent ones. State which next choice can be pruned using only the last chosen bit.