Problem overview
The method generateParentheses(n) takes a number of pairs n and returns an array of strings: every well-formed combination of n pairs of parentheses. A string is well-formed when every ( is closed by a later ) and no ) appears without an open ( before it. The string "()()" is well-formed, while ")(" and "(()" are not.
For n = 1 the only answer is ["()"]. For n = 2 there are two: ["(())", "()()"]. For n = 3 there are five: ["((()))", "(()())", "(())()", "()(())", "()()()"]. The constraint is 1 <= n <= 8. The number of results grows quickly: 1, 2, 5, 14, 42, 132, 429 and 1430 for n from 1 to 8 (these are the Catalan numbers).
Approach: build the string one character at a time
A string with n pairs has 2n characters, and each one is either ( or ). The simplest idea is to generate all 2^(2n) strings and keep the well-formed ones. For n = 8 that is 65,536 strings to build and check, to find 1,430 answers. Most of the work is wasted on strings that were already broken after a few characters.
Backtracking avoids that. Build the string left to right, and after each added character ask whether the prefix can still be completed into a well-formed string. If it can't, abandon that branch immediately, since no continuation will rescue it. Two facts make the test easy. Count the opening characters so far as open and the closing ones as closed:
open < closedis fatal. A prefix with more)than(has a closer with nothing to close, and adding characters never repairs that.- Too many unclosed
(is fatal too. The surplusopen - closedstill has to be closed, and only the remaining slots can hold closers. If the surplus is larger than the number of slots left, the prefix is doomed.
With both checks in place, every string that reaches full length is balanced, so nothing needs to be validated at the end.
Take n = 2, so the target length is 4. The search starts at "" and tries (, then ((. From (( adding another ( gives (((, which has a surplus of 3 with only 1 slot left, so it is dropped. Adding ) gives ((), then (()), which is complete and is saved. Going back to ( and adding ) gives (), and the search continues to ()(). A branch such as ()) has open < closed and is dropped at once, and so is a string starting with ). Because ( is tried before ) at every step, the results come out in the same order as the examples above.
Step by step
- Create the results array on
this.generateParenthesesassignsthis.solutions = [], so the recursive helper can push into it without returning anything. Doing this at the start of every call keeps results of an earlier call out of the next one. - Start the recursion with an empty string, the target length
2 * n, and zero for both counts, then returnthis.solutions. - Declare the helper
generate(current, n, open, closed). Inside it,nis the full length of the string (twice the number of pairs), not the number of pairs. - Prune the first bad case: return if
open < closed. - Prune the second bad case: return if
open > closed + (n - current.length + 1). The slots left aren - current.length, and even if all of them become),closedgrows by at most that much. - Save complete strings: when
current.length == n, pushcurrentand return. The two prunes guarantee that a full-length string here is balanced. - Try
(by recursing withcurrent + '('andopen + 1. - Try
)by recursing withcurrent + ')'andclosed + 1.
The solution in JavaScript
class Solution {
generate(current, n, open, closed) {
if (open < closed) {
return;
}
if (open > closed + (n - current.length + 1)) {
return;
}
if (current.length == n) {
this.solutions.push(current);
return;
}
this.generate(current + '(', n, open + 1, closed);
this.generate(current + ')', n, open, closed + 1);
}
generateParentheses(n) {
this.solutions = [];
this.generate("", 2 * n, 0, 0);
return this.solutions;
}
}
Some details in the code deserve a closer look:
- The
+ 1in the second prune never changes the outcome. The numbersopen + closedandcurrent.lengthare equal, soopen - closedhas the same parity as the length so far. Sincenis even, the slots left have that parity too. So the surplus can never be exactly one more than the slots left, and "greater than slots left plus one" prunes exactly the same prefixes as "greater than slots left". - Strings are immutable in JavaScript.
current + '('builds a new string and leavescurrentalone. That is why there is no explicit "undo" step after the recursive calls, which backtracking code over an array would need: each branch has its own string, and the caller'scurrentis untouched when the next branch starts. - Methods are reached through
this. The helper is called asthis.generate(...), and the results live inthis.solutions, a property created on the object by the assignment ingenerateParentheses.
Complexity
The search tree only contains prefixes that can still be completed, and each complete string is one of the Catalan-number answers, C(n) = (2n)! / (n! (n+1)!). The count of recursive calls for n from 1 to 4 is 5, 13, 35 and 101, and for n = 8 it is 10,975. The time is therefore roughly the number of answers times the string length, since every answer has 2n characters and each + copies the prefix. The number of answers grows like 4^n / (n * sqrt(n)), so the time is exponential in n, which the limit n <= 8 keeps small.
The extra space apart from the output is the recursion stack, 2n calls deep, plus the strings being built: O(n) calls, each holding a string of up to 2n characters. The output array itself holds every answer.
Edge cases and common mistakes
- Passing the number of pairs as the length. The helper compares
current.lengthwithn, so it needs2 * n. Withnpairs it would stop halfway. - Forgetting to reset
this.solutions. If the array were created once, a second call on the same object would return the old answers as well. Creating it insidegenerateParenthesesavoids that. - Dropping the
open < closedcheck. Strings such as"())("would reach full length and be saved, because their counts are equal. Equal counts are not enough: the order matters at every prefix. - Dropping the second prune. Strings such as
"(((("would reach full length and be saved, because they never have more closers than openers. The output would then contain unbalanced strings. - Returning the result of the recursive calls. The helper's job is to push into
this.solutions. Its return value is not used.
Testing
Try these in the editor:
generateParentheses(1)returns["()"].generateParentheses(2)returns["(())", "()()"].generateParentheses(3)returns the five strings listed above.generateParentheses(8).lengthis1430.
