c - 显示没有连续 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] = '\0';
        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);
}