Problem overview
Given n pairs of parentheses, generateParentheses(int n) returns every string of 2 * n characters in which the parentheses are well-formed: each ( is closed by a later ), and no ) appears without an open ( to match. The strings may be in any order in principle, but the lesson's examples list them with ( tried before ).
- For
n = 1the only answer is["()"]. - For
n = 2the answers are(())and()(). - For
n = 3there are five:((())),(()()),(())(),()(())and()()().
The input is small, 1 <= n <= 8, because the number of answers grows quickly: 1, 2, 5, 14, 42, 132, 429 and 1430 for n = 1 through 8. These are the Catalan numbers.
Approach: build the string one character at a time
A string of length 2n has 2^(2n) possible combinations of the two characters, and most are invalid. Generating all of them and filtering would waste almost all the work. Backtracking builds each string character by character and abandons a partial string as soon as it can no longer be completed into a valid one.
Two counters track the partial string: open, the number of ( so far, and closed, the number of ). A prefix is only useful if it passes two tests:
- Never more closes than opens. If
closedexceedsopenat any point, some)has no partner, and adding characters can never fix that. - Not too many opens for the space left. Each extra open parenthesis needs a close later. If
open - closedis larger than the number of positions still to fill, there is no room to close them all.
Because both tests are checked on every prefix, any string that reaches full length has equal numbers of each character and never dips below zero. Together that is the definition of well-formed, so no extra validation is needed at the end.
Step by step
- Keep the results in a field. A field
List<String> solutionslets the recursive helper add answers without passing the list through every call. - Reset it on each call. At the start of
generateParentheses, assign a newArrayListso results from an earlier call do not leak into this one. - Start the recursion. Call
generate("", 2 * n, 0, 0): an empty string, the target length, and zero opens and closes. Inside the helper the parameter namednis the full length, twice the number of pairs. - Return
solutionsonce the recursion has filled it. - Write the helper
void generate(String current, int n, int open, int closed). - First prune: if
open < closed, return. - Second prune: if
openexceedsclosedby more than the positions left, return. The positions left aren - current.length(). - Base case: if
current.length() == n, the string is complete. Add it tosolutionsand return. - Branch twice: recurse with
current + '('andopen + 1, then withcurrent + ')'andclosed + 1.
The solution in Java
class Solution {
void generate(String current, int n, int open, int closed) {
if (open < closed) {
return;
}
if (open > closed + (n - current.length() + 1)) {
return;
}
if (current.length() == n) {
solutions.add(current);
return;
}
generate(current + '(', n, open + 1, closed);
generate(current + ')', n, open, closed + 1);
}
List<String> solutions;
public List<String> generateParentheses(int n) {
solutions = new ArrayList<>();
generate("", 2 * n, 0, 0);
return solutions;
}
}
The code uses List and ArrayList, which live in java.util, so a standalone program needs import java.util.*; at the top.
Tracing n = 2
The helper receives 4 as its length. From the empty string, the call for ")" returns at once because open < closed, and the call for "(" continues. From "(" the helper tries "((" and "()". The string "(((", one step below "((", is pruned: it has three opens and no closes, a surplus of 3 with only one position left. "(()" survives and can only grow into "(())", because "(()(" is pruned in turn. From "()" the only survivor is "()()", since "())" has more closes than opens. The two results are (()) and ()(). Because ( is always tried before ), the answers come out in that order.
Java details
- Strings are immutable.
current + '('creates a new string and leavescurrentunchanged. That is why no "undo" step is needed after the first recursive call: the second call still sees the original prefix. With aStringBuilderyou would have to remove the last character after each call. - Adding a
charto aString.current + '('appends the character. This is fine becausecurrentis aString; with twocharvalues,'(' + ')'would add their numeric codes instead. - The extra
+ 1in the second prune. It never changes the outcome. The surplusopen - closedand the number of positions left always have the same parity, so the surplus can't be exactly one more than the positions left. - The field is shared. Because
solutionsbelongs to the object, callinggenerateParenthesesfrom two threads on the sameSolutionwould mix their results. Resetting it at the start of each call handles the sequential case.
Complexity
The number of results is the Catalan number C(n), roughly 4^n divided by n^1.5 for large n. The pruning is exact: every prefix that survives can still be completed, so the recursion never explores a dead end deeper than one call. The work is therefore proportional to the number of surviving prefixes, each of which also costs up to O(n) to build, because a string concatenation copies the characters. The total time grows like C(n) times a small polynomial in n, and the output alone takes 2n * C(n) characters. The recursion goes at most 2n levels deep, so the space is O(n) not counting the output.
Edge cases and common mistakes
- Counting positions with the wrong
n. Mixing up the number of pairs and the string length is the classic error. In the helper,nis the length, so the base case iscurrent.length() == n, not2 * n. - Forgetting to reset the field. Without
solutions = new ArrayList<>(), a second call to the method returns the first call's results as well. - Checking validity only at the end. That also works but visits every one of the
2^(2n)strings; pruning is what makes the search fast. - Printing the result. To print each combination on its own line, loop over the list:
for (String s : generateParentheses(3)) System.out.println(s);.
