Npairs of Binary Numbers
1, your task is to generate all possible combinations such that for each
0there should be a corresponding
1in the combination not vice versa. In simple words for every
0on the left there should be a
1on the right.
0011" is a valid combination as for both zeros there are two
1'spresent in the right.
0110" is not a valid combination as there is a
1for the first
1is present for the last
0on its right.
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.
The problem becomes simple to understand if consider
0as left bracket "
(" and 1 as right bracket "
Now we just need to balance these brackets in all possible ways.
N = 3, such possible combinations can be:
Can we use
Recursion here ?
Recursionseem to be a great option whenever we need to find different combinations.
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.
Onesfor number of zeros and ones, both set to
i = 0for 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
On each recursive call, check if
Zeros > Onesand
Zerosis less than half of
N, this implies that
Zerosis 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
1to the current string
Zerosis equal to
Ones, we can only add
(when all zeros are used / zeroes are in majority
), we can add
STATE SPACE TREE:
The space complexity can be reduced to
Staticvariable is used to store the output string.
Refer Video for Quick Explaination: