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
- 1 ≤ n ≤ 15
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
- Build the string one character at a time.
- 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