{"id":791,"date":"2020-06-10T11:54:37","date_gmt":"2020-06-10T11:54:37","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=791"},"modified":"2022-03-23T22:53:35","modified_gmt":"2022-03-23T22:53:35","slug":"generate-all-pairs-of-0-and-1","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/generate-all-pairs-of-0-and-1\/","title":{"rendered":"Generate all Pairs of 0 and 1"},"content":{"rendered":"

\"\"<\/p>\n

CONCEPTS USED:<\/h3>\n
\n

Recursion<\/p>\n<\/blockquote>\n

DIFFICULTY LEVEL:<\/h3>\n
\n

Hard<\/p>\n<\/blockquote>\n

PROBLEM STATEMENT(<\/code>SIMPLIFIED)<\/code>:<\/h3>\n
\n

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

"0011<\/code>" is a valid combination as for both zeros there are two 1's<\/code> present in the right. <\/p>\n

"0110<\/code>" is not a valid combination as there is a 1<\/code> for the first 0<\/code> but no 1<\/code> is present for the last 0<\/code> on its right. <\/p>\n<\/blockquote>\n

<\/strong><\/u><\/a><\/p>\n

For Example :<\/h4>\n
N = 1\n\nOutput : 1\n\nExplanation :\n\nAll 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.<\/code><\/pre>\n
N = 2\n\nOutput : 2\n\nExplanation :\n\nAll possible combination of pair 2 = "0011", "0101" \nNotice here that for every 0 on the left there is a 1 on the right.<\/code><\/pre>\n
OBSERVATION:<\/h3>\n
\n
    \n
  1. \n
    The problem becomes simple to understand if consider 0<\/code> as left bracket "(<\/code>" and 1 as right bracket ")<\/code>".  <\/p>\n<\/li>\n
  2. \n
    Now we just need to balance these brackets in all possible ways.<\/p>\n<\/li>\n
  3. \n
    For N = 3<\/code>, such possible combinations can be:
    \n((()))<\/code>,
    \n(()())<\/code>,
    \n(())()<\/code>,
    \n()(())<\/code>,
    \n()()()<\/code><\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
    Can we use Recursion<\/code> here ?<\/em><\/strong>  <\/p>\n
    \n
    Yes<\/strong>, Recursion<\/code> seem to be a great option whenever we need to find different combinations. <\/p>\n<\/blockquote>\n
    SOLVING APPROACH:<\/h3>\n
    \n
      \n
    1. \n
      We will follow a recursive approach to solve the problem.  <\/p>\n<\/li>\n
    2. \n
      Initialize an empty string Str = ""<\/code> for keeping our resultant string.  <\/p>\n<\/li>\n
    3. \n
      Initialize Zeros<\/code>, Ones<\/code> for number of zeros and ones, both set to 0<\/code> initially.  <\/p>\n<\/li>\n
    4. \n
      Keep i = 0<\/code> for tracking on which index we are currently on, whenever we reach i = N<\/code>, this implies we have processed the entire string of length N<\/code>, just print the Str<\/code> and return.  <\/p>\n<\/li>\n
    5. \n
      On each recursive call, check if Zeros > Ones<\/code> and Zeros<\/code> is less than half of N<\/code>, this implies that Zeros<\/code> is more in number in the current string and also some 0<\/code>‘s still remain for getting into the string, in this case, we can either add 0<\/code> or 1<\/code> to the current string Str<\/code>, increment i<\/code> by 1<\/code> and increment Zeros\/Ones<\/code> by 1<\/code> whoever added.  <\/p>\n<\/li>\n
    6. \n
      Else if Zeros<\/code> is equal to Ones<\/code>, we can only add 0<\/code> to Str<\/code>, increment i<\/code> and Zeros<\/code> by 1<\/code>.  <\/p>\n<\/li>\n
    7. \n
      Else(<\/code>when all zeros are used \/ zeroes are in majority)<\/code>, we can add 1<\/code> to Str<\/code> and increment Ones<\/code> and i<\/code> by 1<\/code>.<\/p>\n<\/li>\n<\/ol>\n<\/blockquote>\n
      STATE SPACE TREE:<\/h3>\n
      \"\"
      \n\"\"<\/p>\n
      SOLUTIONS:<\/h4>\n\t\t\t\t\t\t