Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

Practice › Recursion & Backtracking

Binary Strings Without Consecutive 1s

Medium · Recursion & Backtracking · Asked at Amazon, Microsoft, Zoho

Print all binary strings of length n that do not contain two consecutive 1s, in lexicographic (dictionary) order, one per line.

Input

A single integer n.

Output

The strings, one per line.

Constraints

Build the string character by character: you can always append 0, but append 1 only if the last character is not 1. Trying 0 before 1 gives lexicographic order.

Example 1

Input

3

Output

000
001
010
100
101

Example 2

Input

1

Output

0
1

Hints

  1. Build the string one character at a time.
  2. Appending 0 is always allowed; appending 1 is allowed only if the previous character is not 1. Try 0 first to get lexicographic order.

Approach

Recursive generator go(cur): when cur has length n, print it. Otherwise recurse with cur + "0", and — only if cur does not end with 1 — with cur + "1". Because "0" < "1" and we always try 0 first, the strings come out sorted. The number of strings is a Fibonacci number (F(n+2)), so the output stays small.

Complexity: O(F(n+2) · n) time · O(n) recursion depth

Solution

C++ solution

#include <bits/stdc++.h>
using namespace std;

int n;
string out;

void go(string &cur) {
    if ((int)cur.size() == n) {
        out += cur + "\n";
        return;
    }
    cur.push_back('0');
    go(cur);
    cur.pop_back();
    if (cur.empty() || cur.back() != '1') {
        cur.push_back('1');
        go(cur);
        cur.pop_back();
    }
}

int main() {
    cin >> n;
    string cur;
    go(cur);
    cout << out;
    return 0;
}

Python solution

n = int(input())
out = []


def go(cur):
    if len(cur) == n:
        out.append(cur)
        return
    go(cur + "0")
    if not cur.endswith("1"):
        go(cur + "1")


go("")
print("\n".join(out))

Java solution

import java.util.*;

public class Main {
    static int n;
    static StringBuilder out = new StringBuilder();

    static void go(String cur) {
        if (cur.length() == n) {
            out.append(cur).append('\n');
            return;
        }
        go(cur + "0");
        if (!cur.endsWith("1")) go(cur + "1");
    }

    public static void main(String[] args) {
        n = new Scanner(System.in).nextInt();
        go("");
        System.out.print(out);
    }
}

Solve Binary Strings Without Consecutive 1s online · All practice problems