Start practising

Generate all binary strings without consecutive 1's

Medium Recursion & Backtracking Pick / Not-Pick Original on GeeksforGeeks

Generate all binary strings without consecutive 1's is a medium recursion & backtracking problem solved with the pick / not-pick pattern. The best approach, optimal (pick / not-pick with a constraint), runs in O(n · F(n)) time and O(n) space. Below are 2 approaches in Java, from generate all, then filter up.

Problem

NoteLearn how to skip indices in recursion

Generate every binary string of length n that has no two consecutive 1s, in lexicographic order. The point is learning to skip invalid branches in a recursion instead of filtering afterwards.

Examples

Example 1

Input
n = 3
Output
000 001 010 100 101

Example 2

Input
n = 1
Output
0 1

Constraints

  • 1 <= n <= 20
  • Print or return the strings in lexicographic order.

Animated walkthrough

A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.

Concepts first, then the problem and every approach, step by step.

Space to play or pause · ← → to jump a step · click or drag the bar to seek

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.

ApproachTimeSpace
Generate all, then filterO(n · 2ⁿ)O(n)
Optimal (pick / not-pick with a constraint)O(n · F(n))O(n)

1Generate all, then filter

TimeO(n · 2ⁿ)
SpaceO(n)

Generate all 2ⁿ binary strings and keep those without "11".

  1. For mask in 0..2ⁿ - 1, build the string and skip it if it contains 11.
Java
class Solution {
    public List<String> generateBinaryStrings(int n) {
        List<String> out = new ArrayList<>();
        for (int mask = 0; mask < (1 << n); mask++) {
            StringBuilder sb = new StringBuilder();
            for (int i = n - 1; i >= 0; i--) sb.append((mask >> i) & 1);
            if (!sb.toString().contains("11")) out.add(sb.toString());
        }
        return out;
    }
}

2Optimal (pick / not-pick with a constraint)

TimeO(n · F(n))F(n) ≈ 1.618ⁿ valid strings, each built in O(n).
SpaceO(n)

Build the string left to right. Always try 0. Try 1 only when the previous character is 0 or there is none. Invalid branches are never generated, so the work matches the size of the output.

  1. If the position equals n, record the string.
  2. Place 0 and recurse.
  3. If the previous char is not '1', place 1 and recurse.
Java
class Solution {
    public List<String> generateBinaryStrings(int n) {
        List<String> out = new ArrayList<>();
        build(new char[n], 0, out);
        return out;
    }

    private void build(char[] s, int i, List<String> out) {
        if (i == s.length) { out.add(new String(s)); return; }
        s[i] = '0';
        build(s, i + 1, out);
        if (i == 0 || s[i - 1] != '1') {
            s[i] = '1';
            build(s, i + 1, out);
        }
    }
}

Edge cases to test

  • n = 1
  • The count grows like the Fibonacci numbers

Hints

Hint 1

At each position you can always place 0. You can place 1 only if the previous character is not 1.

FAQ

What is the best time complexity for Generate all binary strings without consecutive 1's?

Optimal (pick / not-pick with a constraint) runs in O(n · F(n)) time and O(n) extra space. F(n) ≈ 1.618ⁿ valid strings, each built in O(n).

Which pattern does Generate all binary strings without consecutive 1's use?

It is a recursion & backtracking problem that uses the pick / not-pick pattern. Other problems with the same pattern: Subsets (2 choices per element), Subsets II, Combinations.

Is there a brute force solution for Generate all binary strings without consecutive 1's?

Yes. Generate all, then filter takes O(n · 2ⁿ) time and O(n) space. Generate all 2ⁿ binary strings and keep those without "11".

Which edge cases should I test for Generate all binary strings without consecutive 1's?

n = 1; The count grows like the Fibonacci numbers.