# Generate all binary strings from given pattern

## The given input string consists of 0, 1 and ? (wildcard char), we need to generate all possible binary strings by replacing ? with ‘0’ and ‘1’.

### Examples

a) Input string : “1?1”
Output : 101, 111

b) Input string : 1?0?1?1
Output : 1000101
1000111
1001101
1001111
1100101
1100111
1101101
1101111

Time complexity : O(logn)

## Algorithm

We use recursion,

1. If current character is ?,. we replace it by ‘0’ or ‘1’.

2. If we find ? we replace with ‘0’ and continue recursion.

3. Then, replace ? with ‘1’ and continue recursion

4. We recurse for remaining characters.

5. We print the string if we reaches its end.

## C++ Program

``````#include <bits/stdc++.h>

using namespace std;

void PrintStrings(string str, int index)
{
if(index == str.size())//Print if it reaches the end.
{
cout << str << endl;
return;
}

if(str[index] == '?')//If ?
{
str[index] = '0';//Replace with '0' and continue recursion
PrintStrings(str, index + 1);
str[index] = '1';//Replace with '1' and continue recursion
PrintStrings(str, index + 1);
}
else//If 0 or 1  move forward
{
PrintStrings(str, index + 1);
}
}

//Main function
int main()
{
string Input_string = "1?0?1?1";
PrintStrings(Input_string, 0);
return 0;
}``````

Scroll to Top