Write a program that generates all binary strings without consecutive 1’s. Use recursive function to generate the strings.
Thus, given an integer K, the task is to print all binary strings of size k without consecutive binary 1’s.
Examples:
Input : K = 3
Output : 000 , 001 , 010 , 100 , 101
Input : K = 4
Output :0000 0001 0010 0100 0101 1000 1001 1010
Solution:
#include<stdio.h>
#include<stdlib.h>
void gResult(int K, char str[], int n){
if (n == K){
str[n] = '\0' ;
printf("%s ", str);
return ;
}
if (str[n-1] == '1'){
str[n] = '0';
gResult (K , str , n+1);
}
if (str[n-1] == '0'){
str[n] = '0';
gResult(K, str, n+1);
str[n] = '1';
gResult(K, str, n+1) ;
}
}
void gString(int K ){
if (K <= 0){
return ;
}
char str[K];
str[0] = '0' ;
gResult( K , str , 1 ) ;
str[0] = '1' ;
gResult ( K , str , 1 );
}
int main(){
int k;
while(1){
printf("K = ");
scanf("%d", &k);
gString(k) ;
printf("\n");
}
}