Find all strings of given length containing balanced parentheses

Given a positive number n, find all strings of length n containing balanced parentheses.

 

For example,


Input:  n = 4
Output:
(())
()()

Input:  n = 6
Output:
((()))
(()())
(())()
()(())
()()()

Input:  n = 5
Output: Invalid input

 


 

We can use recursion to solve this problem. The idea is to maintain count of open parenthesis in the output string. Then

  • We recuse with open parentheses with one less character and increased count of open parentheses.
  • We recuse with closed parentheses only if output string has at-least one open parentheses. We recuse with one less character and decreased count of open parentheses.

If desired length n is reached and output string contains all balanced parenthesis, we print it. We return if we cannot close all open parentheses with left characters. Also if number of characters is odd and there is no open parentheses, balanced parentheses cannot be formed.

 
C++ implementation –
 

Download   Run Code

Output:

((()))
(()())
(())()
()(())
()()()

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂