Print All Possible Valid Combinations Of Parenthesis of Given ‘N’

Objec­tive: Given “n”, generate all valid parenthesis strings of length “2n”.
Example:

Given n=2

Output:
(())
()()

Approach:

  • Recursion is the key here.
  • Divide the N into N/2 and N/2 (Count for open and closed parentheses ).
  • Select the open parentheses, add it to the result string and reduce its count and make a recursive call.
  • Select the close parentheses, add it to the result string and reduce its count and make a recursive call.
  • 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.
  • See picture for better explanation.

Generate all valid parenthesis strings of length 2n of given n

Code:


Output:

(())
()()

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

4 Responses

  1. Cherry Zhao says:

    Great analysis. If you want to see another insightful discussion with code, check https://goo.gl/ALZBh0.!

  2. Sergio says:

    Time Complexity O(logN) ?
    Space Complexity O(1) or should I consider the stackframe as space complexity O(logN)?

  3. Abhishek Singh Tomar says:

    if(openP >closeP) // close parantheses is more than open ? how greater than sign is towards the openP

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: