递归(力扣：生成不含相邻零的二进制字符串

题目(生成不含相邻零的二进制字符串)

        给你一个正整数 n。

        如果一个二进制字符串 x 的所有长度为 2 的子字符串中包含 至少 一个 "1"，则称 x 是一个 有效 字符串。

        返回所有长度为 n 的 有效 字符串，可以以任意顺序排列。

思路

        根据题目要求两相邻位不能同时为零，我们可以尝试通过递归的方式生成满足特定条件的二进制字符串组合，并将符合条件的字符串复制到结果数组中。

        可以把整个过程想象成是通过深度遍历构建一棵二叉树，树的每一层代表字符串中的一个位置（索引），每个节点有两条分支，分别对应在该位置设置字符为 '0' 和 '1' 的情况，我们默认优先尝试'0'的情况，过程如下：

图示(n=3)

结果为

        res[0] = 010

        res[1] = 011

        res[2] = 101

        res[3] = 110

        res[4] = 111

Code

#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <string.h>

//复制输入字符串
char* theCopy(const char* str){
    if(str == NULL){
        return NULL;
    }
    size_t length = strlen(str) + 1;//计算输入字符串的长度（包括终止符 '\0'）
    char *copy = (char*)malloc(length * sizeof(char));
    if(copy == NULL){
        return NULL;
    }else{
        return strcpy(copy,str);
    }
}
//递归地生成所有可能的二进制字符串，并将它们存储在 res 数组中
void structure(char* arr,int index,int n,char** res,int* count){
    if(index == n){
        //如果 index 等于 n，表示一个完整的字符串已经生成，将其复制到 res 数组中，并增加计数器,并返回至上一级递归。
        res[*count] = theCopy(arr);
        (*count)++;
        return;
    }else if(index == 0 || arr[index - 1] == '1'){
        //当个索引在初始位置或前一位为'1'则将索引位置替换为'0'，并进入下一级递归
        arr[index] = '0';
        structure(arr,index + 1,n,res,count);
    }
    //将索引位置替换为'1'，再次进入递归
    arr[index] = '1';
    structure(arr,index + 1,n,res,count);
}
char** validStrings(int n, int* returnSize) {
    //创建一个二维数组，用字符串存储所有满足条件的二进制数
    char** res = (char**)malloc(pow(2,n) * sizeof(char*));
    char* arr = (char*)malloc((n + 1) * sizeof(char));
    arr[n] = '\0';//字符串最后以'\0'结尾
    *returnSize = 0;
    structure(arr,0,n,res,returnSize);
    free(arr);
    return res;
}
//测试：
int main() {
    int n = 3; // 你可以根据需要修改这个值来生成不同长度的二进制字符串
    int returnSize;
    char** binaryStrings = validStrings(n, &returnSize);
 
    // 打印生成的二进制字符串
    for (int i = 0; i < returnSize; i++) {
        printf("%s\n", binaryStrings[i]);
    }
 
    // 释放动态分配的字符串数组
    for (int i = 0; i < returnSize; i++) {
        free(binaryStrings[i]);
    }
    free(binaryStrings);
 
    return 0;
}