Two choices per position gives the smallest possible backtracking program.
What to build
A recursive program that prints every string of n binary digits.
Requirements
- Fill one position at a time.
- Try 0 before 1, so the strings come out in increasing order.
- Print one string per line.
Input
One number n.
Output
2ⁿ lines, each with n digits and no spaces.
Constraints
1 ≤ n ≤ 8.
Example
Input:
2
Output:
00
01
10
11
Why it works
Each position has two choices, so the search has 2ⁿ leaves. Trying 0 first means every string starting with 0 is printed before any starting with 1.
Examples
Example 1 · Input
2
Expected output
00 01 10 11
Example 2 · Input
1
Expected output
0 1
Hints
Hint 1
Write a function `go(i)` that decides position `i`.
Hint 2
Put 0 at position `i` and recurse, then put 1 there and recurse. When `i == n`, print the string.
Solution
Show one correct solution (try it yourself first)
#include <stdio.h>
int n;
int digit[8];
void go(int i) {
if (i == n) {
for (int k = 0; k < n; k++) printf("%d", digit[k]);
printf("\n");
return;
}
digit[i] = 0;
go(i + 1);
digit[i] = 1;
go(i + 1);
}
int main(void) {
scanf("%d", &n);
go(0);
return 0;
}