Generate all binary strings without consecutive 1's

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;
}
Try It

 


Next > < Prev
Scroll to Top