Recursion: Given a number, generate all binary strings.

Problem Statement:

You are given a number, you need to generate all binary strings that do not have consecutive 1s and in increasing order

Example:

Input: n = 3

Output:

["000", "001", "010", "100", "101"]

Solution Explanation:

We will use recursion to solve the problem.

At each position, we have a choice to place 0 or 1.

Then from the question, you can place 0 freely.

To insert 1, you need to check if previous char is not 1

Then continue with recursion, till the length of the string becomes n and get the strings.

Time Complexity: O(2^n) as each position has 2 choices
Space Complexity: O(n)

Code Solution

#include <iostream>
#include <vector>
#include <queue>
#include <stack>
using namespace std;


void solution(string s, int n, vector<string>&ans)
{
    if(s.size() == n)
    {
        ans.push_back(s);
        return;
    }

    solution(s+'0', n, ans);
    if(s.empty() || s.back()!='1')
        solution(s+'1', n, ans);
}

int main() 
{
    int n = 3;

    vector<string> result;

    solution("", n, result);

    for (string& s : result) 
    {
        cout << s << " ";
    }
    cout << endl;
    return 0;
}

Output

000 001 010 100 101