Find all strings of a given length containing balanced parentheses
Given a positive number n, find all strings of length n containing balanced parentheses.
For example,
Output:
(())
()()
Input: n = 6
Output:
((()))
(()())
(())()
()(())
()()()
Input: n = 5
Output: Invalid input
We can use recursion to solve this problem. The idea is to maintain a count of the open parenthesis in the output string. Then
- Recur with open parentheses with one less character and an increased count of open parentheses.
- Recur with closed parentheses only if the output string has at least one open parenthesis. And recur with one less character and a decreased count of open parentheses.
If the desired length n is reached and the output string contains all balanced parenthesis, print it. Return if we cannot close all open parentheses with left characters. Also, if the total number of characters is odd and there are no open parentheses, we cannot form the balanced parentheses.
Following is the C++, Java, and Python implementation of the idea:
C++
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 |
#include <iostream> #include <string> using namespace std; // Function to find all strings of length `n` containing balanced parentheses void balParenthesis(int n, string str, int open) { // if `n` is odd with no open parentheses, balanced parentheses // cannot be formed if ((n & 1) && !open) { return; } // base case: length `n` is reached if (n == 0) { // if the output string contains all balanced parenthesis, print it if (open == 0) { cout << str << endl; } return; } // Optimization: return if we cannot close all open parentheses with // left characters if (open > n) { return; } // recur with open parentheses balParenthesis(n - 1, str + "(", open + 1); // recur with closed parentheses only if the output string has at least // one unclosed parentheses if (open > 0) { balParenthesis(n - 1, str + ")", open - 1); } } int main() { int n = 6; balParenthesis(n, "", 0); return 0; } |
Output:
((()))
(()())
(())()
()(())
()()()
Java
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 |
class Main { // Function to find all strings of length `n` containing balanced parentheses public static void balParenthesis(int n, String str, int open) { // if `n` is odd with no open parentheses, balanced parentheses // cannot be formed if ((n & 1) == 1 && open == 0) { return; } // base case: length `n` is reached if (n == 0) { // if the output string contains all balanced parenthesis, print it if (open == 0) { System.out.println(str); } return; } // Optimization: return if we cannot close all open parentheses // with left characters if (open > n) { return; } // recur with open parentheses balParenthesis(n - 1, str + "(", open + 1); // recur with closed parentheses only if the output string has // at least one unclosed parentheses if (open > 0) { balParenthesis(n - 1, str + ")", open - 1); } } public static void main(String[] args) { int n = 6; balParenthesis(n, "", 0); } } |
Output:
((()))
(()())
(())()
()(())
()()()
Python
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 |
# Function to find all strings of length `n` containing balanced parentheses def balParenthesis(n, result=set(), open=0, s=''): # if `n` is odd with no open parentheses, balanced parentheses # cannot be formed if n & 1 and not open: return result # base case: length `n` is reached if n == 0: # if the output string contains all balanced parenthesis, print it if not open: result.add(s) return result # Optimization: return if we cannot close all open parentheses with # left characters if open > n: return result # recur with open parentheses result = balParenthesis(n - 1, result, open + 1, s + '(') # recur with closed parentheses only if the output string has at least # one unclosed parentheses if open > 0: result = balParenthesis(n - 1, result, open - 1, s + ')') return result if __name__ == '__main__': n = 6 result = balParenthesis(n) print(result) |
Output:
{‘()(())’, ‘()()()’, ‘(())()’, ‘(()())’, ‘((()))’}
The time complexity of the above solution is exponential as there are exactly 2n-1 combinations, where n is the length of the input string. It also requires additional space for the recursion (call stack).
Thanks for reading.
To share your code in the comments, please use our online compiler that supports C, C++, Java, Python, JavaScript, C#, PHP, and many more popular programming languages.
Like us? Refer us to your friends and support our growth. Happy coding :)