# Generate all binary strings without consecutive 1’s

0
338

## Given an integer k, write a function to print all binary strings of size k with no consecutive 1’s

### Example

INPUT
k = 3

OUTPUT
“000”, “001”, “101”, “010”, “100”

## Algorithm(recursive algo)

1. If size of the generated string becomes equal to the given size print the string.

2. If the previous character is ‘1’, the put ‘0’ at the end of the string and recursively call function
s[n] = ‘0’;
stringsSizeK(k, s, n+1)

3. If previous character is ‘0’, then put both ‘1’ and ‘0’ at end of string
s[n] = ‘0’
stringsSizeK(k, s, n+1)
s[n] = ‘1’
stringsSizeK(k, s, n+1)

## C++ Program

``````#include <bits/stdc++.h>
using namespace std;
//Recursive function
void stringsSizeKUtil(int K, char s[], int n)
{
// print if sizes are equal
if (n  == K)
{
// terminate binary string
s[n] = '\0' ;
cout << s << " "<<endl;
return ;
}

//If prev char is 1
if (s[n-1] == '1')
{
s[n] = '0';
stringsSizeKUtil (K , s , n+1);
}

//If prev char is 0
if (s[n-1] == '0')
{
s[n] = '0';
stringsSizeKUtil(K, s, n+1);
s[n] = '1';
stringsSizeKUtil(K, s, n+1) ;
}
}

//main function
void stringsSizeK(int K )
{
// Base case
if (K <= 0)
return ;

// One by one stores every binary string of length K
char s[K];

//all strings starting with 0
s[0] = '0' ;
stringsSizeKUtil ( K , s , 1 ) ;

//all strings starting with 1
s[0] = '1' ;
stringsSizeKUtil ( K , s , 1 );
}

int main()
{
int K = 4;
stringsSizeK (K) ;
return 0;
}``````

If you have come this far, it means that you liked what you are reading. I am a software developer (graduated from BITS Pilani). I love writing technical articles on programming and data structures.