# Generate all Pairs of 0 and 1 Recursion

Hard

### PROBLEM STATEMENT`(`SIMPLIFIED`)`:

Given `N` pairs of Binary Numbers `0` and `1`, your task is to generate all possible combinations such that for each `0` there should be a corresponding `1` in the combination not vice versa. In simple words for every `0` on the left there should be a `1` on the right.

"`0011`" is a valid combination as for both zeros there are two `1's` present in the right.

"`0110`" is not a valid combination as there is a `1` for the first `0` but no `1` is present for the last `0` on its right.

See original problem statement here

#### For Example :

``````N = 1

Output : 1

Explanation :

All possible combination of pair 1 = "01", but "10" is not a valid pair as there is no valid 1 for 0 on the right of it.``````
``````N = 2

Output : 2

Explanation :

All possible combination of pair 2 = "0011", "0101"
Notice here that for every 0 on the left there is a 1 on the right.``````

### OBSERVATION:

1. The problem becomes simple to understand if consider `0` as left bracket "`(`" and 1 as right bracket "`)`".

2. Now we just need to balance these brackets in all possible ways.

3. For `N = 3`, such possible combinations can be:
`((()))`,
`(()())`,
`(())()`,
`()(())`,
`()()()`

Can we use `Recursion` here ?

Yes, `Recursion` seem to be a great option whenever we need to find different combinations.

### SOLVING APPROACH:

1. We will follow a recursive approach to solve the problem.

2. Initialize an empty string `Str = ""` for keeping our resultant string.

3. Initialize `Zeros`, `Ones` for number of zeros and ones, both set to `0` initially.

4. Keep `i = 0` for tracking on which index we are currently on, whenever we reach `i = N`, this implies we have processed the entire string of length `N`, just print the `Str` and return.

5. On each recursive call, check if `Zeros > Ones` and `Zeros` is less than half of `N`, this implies that `Zeros` is more in number in the current string and also some `0`‘s still remain for getting into the string, in this case, we can either add `0` or `1` to the current string `Str`, increment `i` by `1` and increment `Zeros/Ones` by `1` whoever added.

6. Else if `Zeros` is equal to `Ones`, we can only add `0` to `Str`, increment `i` and `Zeros` by `1`.

7. Else`(`when all zeros are used / zeroes are in majority`)`, we can add `1` to `Str` and increment `Ones` and `i` by `1`.

### STATE SPACE TREE:  #### SOLUTIONS:

```#include <stdio.h>
#include <string.h>

/* function for appending a char to a char array */
void append(char* s, char c) {
int len = strlen(s);
s[len] = c;
s[len+1] = '\0';
}

//function generating all such combinations
void generatePairs_0_1(int n, int zeros, int ones, char *ans, int i){

// when i becomes equal to string length print the string
if(i == n){
printf("%s ", ans);
return ;
}

/* creating temporary char arrays */
char temp_0;
char temp_1;

/* copying original char array to temp arrays */
strcpy(temp_0, ans);
strcpy(temp_1, ans);

/* append char i to char array str */
append(temp_0, '0');
append(temp_1, '1');

/*when zeros are greater than ones in the left and half of the
zeros are not filled  we can either add 0 or 1 to the string */
if((zeros > ones) && (zeros < n/2)){

generatePairs_0_1(n, zeros + 1, ones, temp_0, i+1);
generatePairs_0_1(n, zeros, ones + 1, temp_1, i+1);
}

/*when zeros are equal to ones, we can only add 0 zero to the string */
else if(zeros == ones){
generatePairs_0_1(n, zeros + 1, ones, temp_0, i+1);
}

/*when zeros are greater than ones but have already been
filled in half of the string, we can now add remaining 1's*/
else
generatePairs_0_1(n, zeros, ones + 1, temp_1, i+1);
}

int main()
{
int n; scanf("%d", &n);

char ans = "";
generatePairs_0_1(n*2, 0, 0, ans, 0);

return 0;
}
```
```#include <bits/stdc++.h>
using namespace std;

//function generating all such combinations
void generatePairs_0_1(int n, int zeros, int ones, string str, int i){

// when i becomes equal to string length print the string
if(i == n){
cout<<str<<" ";
return ;
}

/*when zeros are greater than ones in the left and half of the
zeros are not filled  we can either add 0 or 1 to the string */
if((zeros > ones) && (zeros < n/2)){
generatePairs_0_1(n, zeros + 1, ones, str + "0", i+1);
generatePairs_0_1(n, zeros, ones + 1, str + "1", i+1);
}

/*when zeros are equal to ones, we can only add 0 zero to the string */
else if(zeros == ones){
generatePairs_0_1(n, zeros + 1, ones, str + "0", i+1);
}

/*when zeros are greater than ones but have already been
filled in half of the string, we can now add remaining 1's*/
else
generatePairs_0_1(n, zeros, ones + 1, str + "1", i+1);
}

int main()
{
int n; cin>>n;
generatePairs_0_1(n*2, 0, 0, "", 0);

return 0;
}
```
```import java.util.*;
import java.io.*;

public class Main {
static void generatePairs_0_1(int n, int zeros, int ones, String str, int i){

// when i becomes equal to string length print the string
if(i == n){
System.out.print(str + " ");
return ;
}

/*when zeros are greater than ones in the left and half of the
zeros are not filled  we can either add 0 or 1 to the string */
if((zeros > ones) && (zeros < n/2)){
generatePairs_0_1(n, zeros + 1, ones, str + "0", i+1);
generatePairs_0_1(n, zeros, ones + 1, str + "1", i+1);
}

/*when zeros are equal to ones, we can only add 0 zero to the string */
else if(zeros == ones){
generatePairs_0_1(n, zeros + 1, ones, str + "0", i+1);
}

/*when zeros are greater than ones but have already been
filled in half of the string, we can now add remaining 1's*/
else
generatePairs_0_1(n, zeros, ones + 1, str + "1", i+1);
}

public static void main(String args[]) throws IOException {

Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
String res = "";
generatePairs_0_1(n*2, 0, 0, res, 0);
}
}
```
```def generatePairs_0_1(n, zeros, ones, str, i):

if(i == n):
print(str, end = " ")
return

if((zeros > ones) and (zeros < n//2)):
generatePairs_0_1(n, zeros + 1, ones, str + "0", i+1)
generatePairs_0_1(n, zeros, ones + 1, str + "1", i+1)

elif(zeros == ones):
generatePairs_0_1(n, zeros + 1, ones, str + "0", i+1)

else:
generatePairs_0_1(n, zeros, ones + 1, str + "1", i+1)

n = int(input())
generatePairs_0_1(n*2, 0, 0, "", 0)
```

[forminator_quiz id="1134"]

Space Complexity: `O(N)`

The space complexity can be reduced to `O(N)` if `Global` variable or `Static` variable is used to store the output string.

#### Refer Video for Quick Explaination: This article tried to discuss Recursion. Hope this blog helps you understand and solve the problem. To practice more problems on Recursion you can check out MYCODE | Competitive Programming.