# 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 –

Output:

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