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 recurse with open parentheses with one less character and increased count of open parentheses.
     
  • We recurse with closed parentheses only if output string has at-least one open parentheses. We recurse 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.

 
Below is C++ and Java implementation of the idea –

C++

Download   Run Code

Java

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 🙂

Get great deals at Amazon




Leave a Reply

Notify of
avatar
wpDiscuz