#### CONCEPTS USED:

Recursion

#### DIFFICULTY LEVEL:

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:

The problem becomes simple to understand if consider

`0`

as left bracket "`(`

" and 1 as right bracket "`)`

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

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:

We will learn programming languages online and follow a recursive approach to solve the problem.

Initialize an empty string

`Str = ""`

for keeping our resultant string.Initialize

`Zeros`

,`Ones`

for number of zeros and ones, both set to`0`

initially.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.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.Else if

`Zeros`

is equal to`Ones`

, we can only add`0`

to`Str`

, increment`i`

and`Zeros`

by`1`

.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:

[TABS_R id=916]

[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: