Free lessonsBacktracking · Stage 0 · Build, check, undo · Step 1

Generate binary strings

Make a choice, explore the consequences, and backtrack to try the other choice. About 8 minutes.

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

res = []
def backtrack(curr):
    if len(curr) == n:
        res.append("".join(curr))
        return
    for ch in ("0", "1"):
        curr.append(ch)
        backtrack(curr)
        curr.pop()
backtrack([])
return res

Quick check

How many strings of length n = 4 are generated?

A16 strings
B8 strings
C4 strings

Show the answer

16 strings. 2^4 = 16 distinct combinations.

Your problem

Generate binary strings

Given a non-negative integer n, generate all binary strings of length n in lexicographical order. A binary string is a string consisting only of the characters '0' and '1'.

Example

n = 2 → ["00", "01", "10", "11"]

0 ≤ n ≤ 12

Solve it in your browserPython, C++, Java or JavaScript. Hints if you get stuck. No sign-up needed.

Start coding