Print every binary string of length n that has no two 1s side by side.
What to build
A recursive function that builds strings one character at a time, and goes back to try other choices.
Requirements
- Read
n. - Print each valid string on its own line, in increasing order.
Input
One whole number n.
Output
One line per string.
Constraints
n is from 1 to 12.
Example
Input:
1
Output:
0
1
Why it works
Trying 0 before 1 at each position gives the strings in order. Checking the previous character cuts off a whole branch as soon as it becomes invalid.
Examples
Example 1 · Input
1
Expected output
0 1
Example 2 · Input
2
Expected output
00 01 10
Hints
Hint 1
Keep a char array, and a position that says which character to choose next.
Hint 2
You can always place a 0 next.
Hint 3
You can place a 1 only if the previous character is not a 1.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
char text[20];
int n;
void build(int position) {
if (position == n) {
printf("%s\n", text);
return;
}
text[position] = '0';
build(position + 1);
if (position == 0 || text[position - 1] != '1') {
text[position] = '1';
build(position + 1);
}
}
int main(void) {
scanf("%d", &n);
text[n] = '\0';
build(0);
return 0;
}