Problem overview
The method generateParentheses receives n, a number of pairs, and returns every well-formed string made of n opening and n closing parentheses. A string is well-formed when every ( is closed by a later ) and no ) appears before its partner. For example, "(())" and "()()" are well-formed, while ")(" and "(()" are not. The statement limits n to 1 through 8.
For n = 3 the answer has five strings: ["((()))", "(()())", "(())()", "()(())", "()()()"]. For n = 1 it is just ["()"].
Approach: build the string one character at a time
A string of length 2 * n has two choices at every position, so there are 2^(2n) candidates. Building them all and checking each one wastes nearly all the work. It is better to build a string character by character, and stop extending any prefix that can no longer be completed into a well-formed string.
Track two counters along with the current prefix: open, the number of ( so far, and closed, the number of ). Two rules decide whether a prefix is still worth extending:
- Never more closes than opens. If
closedexceedsopenat some point, some)has no partner, and no later characters can repair that. - Not too many unclosed opens. Each
(still unclosed needs a later). Ifopen - closedis more than the number of positions left, the string cannot finish balanced.
When a prefix passes both rules and reaches full length, it is well-formed, since both counters are then consistent: the string has the right length, never closes too early, and has no unclosed opens left. It goes into the results. Otherwise try both characters: append ( and recurse, then append ) and recurse. Because the prefix is a string, and strings are immutable, there is nothing to undo after each call.
Step by step
- Prepare the results. In
generateParentheses, setthis.solutionsto an empty array. The class declaressolutions: string[];at the top, because TypeScript needs every property declared. - Start the search with an empty string, a target length of
2 * nand both counters at 0. - Return
this.solutions. - Declare
generatewithcurrent, the target length (namedninside the helper),openandclosed. Inside the helper,nis the full string length, twice the number of pairs. - Prune closes. If
open < closed, return. - Prune opens. If
openis greater thanclosed + (n - current.length + 1), return. The partn - current.lengthis the number of slots left, and even if all of them are),closedgrows by at most that much. - Record complete strings. When
current.length == n, pushcurrentand return. - Try an opening parenthesis: recurse with
current + '('andopen + 1. - Try a closing parenthesis: recurse with
current + ')'andclosed + 1.
The solution in TypeScript
class Solution {
solutions: string[];
generate(current: string, n: number, open: number, closed: number) {
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: number): string[] {
this.solutions = [];
this.generate("", 2 * n, 0, 0);
return this.solutions;
}
}
The + 1 in the second check looks odd but changes nothing. After current.length characters, open + closed equals that length, so open - closed has the same parity (odd or even) as the length. The target length is even, so the slots left have that same parity too. The surplus of opens therefore can never be exactly one more than the slots left, and "greater than slots + 1" prunes exactly the same prefixes as "greater than slots".
TypeScript details worth knowing:
- Strings are immutable.
current + '('creates a new string and leavescurrentalone. Each recursive call gets its own prefix, so no "remove the last character" step is needed, unlike with an array. - Shared results.
this.solutionsis one array on the object, and every call pushes into it. It is reset at the start of eachgenerateParentheses, so calling the method twice on the same object does not mix the results. - Chars are strings. TypeScript has no separate character type, so
'('and"("are the same kind of value. - Inferred return type.
generatereturns nothing, so TypeScript infersvoid.
Complexity
The number of well-formed strings is the Catalan number, C(2n, n) / (n + 1): 1, 2, 5, 14, 42, 132, 429 and 1,430 for n = 1 to 8.
Time: proportional to the number of search-tree nodes times the cost of building a string. In a test run, n = 8 made 10,975 calls to produce 1,430 results, so pruning keeps the search close to the output size. In general the total grows like 4^n up to a polynomial factor, and each string costs O(n) to build.
Space: the results take O(n) per string. The recursion is at most 2n deep, with a prefix string in each frame.
Edge cases and common mistakes
n = 1. The search finds only"()".- Mixing up
n. IngenerateParenthesesit is the number of pairs; ingenerateit is the string length. The start call passes2 * n. - Checking only at the end. Generating all strings first and validating afterwards also works for tiny
nbut does far more work than pruning. - Allowing a close before its open. Without the first check, strings like
")("would reach full length. The check on each prefix stops them early. - Too many opens. Without the second check, a string like
"((("is only discovered to be hopeless when it reaches full length. - Leftover results. Forgetting to reset
this.solutionswould keep results from a previous call.
Testing
n = 1gives["()"].n = 2gives["(())", "()()"].n = 3gives["((()))", "(()())", "(())()", "()(())", "()()()"].n = 4gives 14 strings, andn = 8gives 1,430.