Problem
Given an integer n, generate all combinations of n pairs of parentheses that are correctly balanced.A combination is valid when every opening parenthesis
( has a corresponding closing parenthesis ), and a closing parenthesis never appears before its matching opening parenthesis.
Example(s)
Consider the following example(s) to understand the expected input and output.Input
n = 3Output
["((()))","(()())","(())()","()(())","()()()"]Solution
This solution uses Backtracking to build valid parentheses combinations one character at a time.Two counters are maintained:
open tracks the number of opening parentheses used, and close tracks the number of closing parentheses used.
open < n. A closing parenthesis can be added only when close < open, ensuring that the number of closing parentheses never exceeds the number of opening parentheses.
When the current string contains 2 × n parentheses, a complete valid combination has been formed and is added to the result.
After each recursive call, the last parenthesis is removed so that the algorithm can explore the next possible choice.
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
backtrack(n, 0, 0, new StringBuilder(), result);
return result;
}
private void backtrack(int n, int open, int close,
StringBuilder current, List<String> result) {
// A complete valid combination is found.
if (current.length() == 2 * n) {
result.add(current.toString());
return;
}
// Add an opening parenthesis.
if (open < n) {
current.append('(');
backtrack(n, open + 1, close, current, result);
// Undo the choice.
current.deleteCharAt(current.length() - 1);
}
// Add a closing parenthesis only when it is valid.
if (close < open) {
current.append(')');
backtrack(n, open, close + 1, current, result);
// Undo the choice.
current.deleteCharAt(current.length() - 1);
}
}
Complexity
The number of valid combinations is the n-th Catalan number, which is approximatelyO(4n / n3/2). Since each generated combination contains 2n characters, the time complexity is O(4n / n1/2) when accounting for constructing each result string.
The recursion depth is
O(n), excluding the space required for storing the output.