显示没有连续 1 的二进制字符串

Question

如何修改下面用来显示所有N位二进制数组合的回溯代码到显示没有连续1的二进制数？例子：输入：N = 2 输出：3 // 3 个字符串分别是 00, 01, 10

输入：N = 3 输出：5 // 5 个字符串分别是 000, 001, 010, 100, 101

#include <stdio.h>

char target[100];
void foo(int size, int count)
{
    if (count > size)
        return;
    if (count == size) {
        target[count] = '[=10=]';
        printf("%s\n", target);
        return;
    }
    if (count < size) {
        target[count] = '1';
        foo(size, count+1);
    }
    target[count] = '0';
    foo(size, count+1);
}

int main()
{
    int n = 3;
    foo(n, 0);
    return 0;
}

Answer 1

如果前一个位置也是“1”，则不要放置“1”。例如：

if (count == 0 || target[count-1] != '1') {
    target[count] = '1';
    foo(size, count+1);
}

显示没有连续 1 的二进制字符串

display binary strings without consecutive 1’s

c

algorithm

recursion

dynamic-programming

backtracking