Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Pinterest
Share On Reddit
Share On Stumbleupon
Contact us
Hide Buttons

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

Objec­tive: - Given “n”, gen­er­ate all valid paren­the­sis strings of length “2n”.
Exam­ple:

Given n=2

Output:
(())
()()

Approach:

  • Recur­sion is the key here.
  • Divide the N into N/2 and N/2 (Count for open and closed parentheses ).
  • Select the open paren­the­ses, add it to the result string and reduce its count and make a recur­sive call.
  • Select the close paren­the­ses, add it to the result string and reduce its count and make a recur­sive call.
  • To print only valid paren­the­ses, make sure at any given point of time, close paren­the­ses count is not less that open paren­the­ses count because it means close paren­the­ses has been printed with its respec­tive open parentheses.
  • See pic­ture for bet­ter explanation.
Generate-all-valid-parenthesis-strings-of-length-2n-of-given-n

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

Code:


Output:

(())
()()

You may also like...