{"id":2079,"date":"2020-07-29T08:32:19","date_gmt":"2020-07-29T08:32:19","guid":{"rendered":"https:\/\/blog.prepbytes.com\/?p=2079"},"modified":"2022-03-28T00:55:07","modified_gmt":"2022-03-28T00:55:07","slug":"balanced-parenthesis-count","status":"publish","type":"post","link":"https:\/\/prepbytes.com\/blog\/balanced-parenthesis-count\/","title":{"rendered":"BALANCED PARENTHESIS COUNT"},"content":{"rendered":"

\"\"<\/p>\n

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

Recursion and Backtracking.<\/p>\n<\/blockquote>\n

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

Medium.<\/p>\n<\/blockquote>\n

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

Rohan is now fond of balanced sequences, but suddenly he realized that he is in love with balanced parenthesis. Now he wants to know the number of the balanced parenthesis of length N. Help Rohan find the count.<\/p>\n<\/blockquote>\n

For Example :<\/h4>\n
N = 4;\nThe balanced parenthesis sequence of length 4 are: (()), ()()\n\nN=6;\nThe balanced parenthesis sequence of length 4 are: ((())), ()()(),()(()),(())(),(()()).<\/code><\/pre>\n
SOLVING APPROACH:<\/h3>\n
BRUTE FORCE:<\/strong><\/p>\n
Generate all (2 ^ (n)) possible parenthese strings and then validate each for being balanced.\n\nIf n = 4 then the string length will be 2 times that since all open parentheses are matched by closed parentheses.\n\nThis lower bounds our time complexity.\n\nEven if we restrict the enumeration to just sets with an equal number of left and right parentheses we will have choose(k, k\/2) strings to consider for validation.<\/code><\/pre>\n
OPTIMIZATION:<\/strong><\/p>\n
\"\"<\/p>\n
You are encouraged to implement the above brute force  on your own first ,before looking at the solution.
\n<\/strong><\/u><\/a><\/p>\n
\n
First, observe the recursion tree shown in the figure closely.Can you observe the key to this problem?
\nThe Key<\/strong> is:<\/p>\n
At each point of constructing the string of length k we make a choice.
\nWe can place a "(" and recurse or we can place a ")" and recurse.
\nBut we can’t just do that placement, we need 2 critical pieces of information.
\nThe amount of left parens left to place.
\nThe amount of right parens left to place.
\nWe have 2 critical rules at each placement step.
\nWe can place a left parentheses if we have more than 0 left to place.
\nWe can only place a right parentheses if there are left parentheses that we can match against.
\nWe know this is the case when we have less left parentheses to place than right parentheses to place.
\nOnce we establish these constraints on our branching we know that when we have 0 of both parens to place that we are done, we have an answer in our base case.<\/p>\n<\/blockquote>\n
ALGORITHM:<\/strong><\/p>\n
\n
1.Recursion is the key here.<\/p>\n
2.Divide the N into N\/2 and N\/2 (Count for open and closed parentheses ).<\/p>\n
3.Select the open parentheses, add it to the result string and reduce its count and make a recursive call.<\/p>\n
4.Select the close parentheses, add it to the result string and reduce its count and make a recursive call.<\/p>\n
5 .To print only valid parentheses, make sure at any given point of time, close parentheses count is not less that open parentheses count because it means close parentheses has been printed with its respective open parentheses.<\/p>\n<\/blockquote>\n
SOLUTIONS:<\/h3>\n
\t\t\t\t\t\t