1236. Every Binary String With No Two Ones Together

Print every string of n characters over 0 and 1 in which no two 1s are next to each other, one per line, in LEXICOGRAPHIC order, which for strings of equal length means comparing them character by character.

n = 4 0000 0001 0010 0100 0101 1000 1001 1010

There are eight of them, which is the Fibonacci number.

## Why the order has to be pinned, and pinned without naming a program

A set of answers has no order. If a statement says only "print them all", two correct programs produce two different outputs and no automated check can tell a correct program from a broken one. So the order is part of the specification.

The second trap is pinning it as "the order your search finds them in". That names a program rather than a rule, and it is not a specification: a search that tries its options in a different sequence finds the same answers in a different order and is equally entitled to call itself correct. The rule below mentions no search.

Here the rule is ordinary lexicographic order, which is unambiguous for strings of the same length, so nothing more needs saying.

## What most people try first

Generate all 2^n strings and keep the ones with no 11 in them. At n = 14 that is 16384 strings to print 987, so six out of seven are built and thrown away. The waste is avoidable because the constraint is visible as soon as the second of two 1s is written.

## Generating directly

Fill the positions left to right, trying 0 then 1, and refuse a 1 when the previous character was a 1:

go(i, prev): if i == n: print the string; return for ch in '0', '1': if ch == '1' and prev == '1': continue write ch at position i; go(i + 1, ch)

Every leaf is an answer, so no work is wasted at all, and trying 0 before 1 makes the output lexicographic with no sorting.

## Why the output is lexicographic

Two different answers differ at some first position, where one has 0 and the other 1. The recursion explores the whole 0 branch at that position before the 1 branch, so the one with 0 is printed first. That is exactly lexicographic order.

## How many there are

Let F(m) count the strings of length m. A string either starts with 0, leaving m - 1 characters free, or starts with 10, leaving m - 2. So F(m) = F(m-1) + F(m-2) with F(0) = 1 and F(1) = 2, which is the Fibonacci sequence shifted: F(m) is the Fibonacci number F(m+2) in the usual numbering where the first two are 1 and 1. At n = 14 that is 987.

This is worth computing before writing the program, because it says how big the output is and therefore whether generating and filtering could ever have been acceptable.

## The settled boundaries

n = 1 has two answers, 0 and 1. There is always at least one answer, the all-zero string, so nothing special is printed for an empty result.

## Cost

One node per valid prefix and every leaf is an answer, so the work is proportional to the output.

Constraints - `1 ≤ n ≤ 14`