Problem overview
Given n pairs of parentheses, generateParentheses(n) returns every well-formed combination as a list of strings. A string is well-formed if every opening parenthesis is closed in the right order, so "(())" and "()()" are well-formed, while ")(" and "(()" are not.
For n = 3 the answer has five strings: "((()))", "(()())", "(())()", "()(())" and "()()()". For n = 1 it is just "()". The lesson states 1 <= n <= 8.
Approach
Build each string one character at a time. At every position we may append '(' or ')', which gives 2^(2n) strings if we try everything. Most of those are not well-formed, so we cut a branch as soon as its prefix can no longer be completed into a valid string.
The lesson tracks two counters, open and closed, for the parentheses used so far, and prunes in two cases:
- More closed than open. If
closedexceedsopen, some')'has nothing to match, and adding more characters can't repair that. - Too many open ones. Each remaining position can add at most one closing parenthesis. If the surplus
open - closedis bigger than the number of positions left, the string can't be balanced by the end.
A string that survives both checks and has reached full length (2 * n characters) has equal counts and never closed too early, so it is well-formed.
Step by step
- A shared result list.
solutionsis alateinitproperty of typeMutableList<String>, so the recursive helper can add to it without returning anything.lateinitpostpones initialization untilgenerateParenthesesruns. - Reset on every call. At the top of
generateParentheses, assign a new empty list so results from earlier calls don't leak in. - Kick off the search with an empty string, the target length
2 * nand both counters at 0, then returnsolutions. - Declare
generatewithcurrent(the string so far),n(the target length, which is twice the number of pairs inside this function) and the countersopenandclosed. - First prune. Return if
open < closed. - Second prune. Return if
open > closed + (n - current.length + 1). - Completion. If
current.length == n, addcurrenttosolutionsand return. - Branch. Recurse with
'('appended andopen + 1, then with')'appended andclosed + 1.
The + 1 in the second prune never changes the outcome. The difference open - closed and the number of free positions n - current.length always have the same parity: both change by one with every character, and both start even. So the surplus can never be exactly one more than the free positions, and the check behaves as if the + 1 were not there.
The solution in Kotlin
class Solution {
fun generate(current: String, n: Int, open: Int, closed: Int) {
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)
}
lateinit var solutions: MutableList<String>
fun generateParentheses(n: Int): List<String> {
solutions = mutableListOf()
generate("", 2 * n, 0, 0)
return solutions
}
}
Kotlin details:
current + '('builds a newStringby appending aChar. Strings are immutable, socurrentis untouched and the second recursive call still sees the original. That means no undo step is needed, unlike other backtracking problems that modify a shared list.- Chars and strings.
'('in single quotes is aChar,"("in double quotes is aString. Both work with+on a string. lateinitworks for avarwith a non-null type such asMutableList<String>. Reading it before assignment throwsUninitializedPropertyAccessException. The reset ingenerateParenthesesis also what makes repeated calls independent.openas a parameter name.openis a modifier keyword in Kotlin: it has a special meaning only before a class or member declaration, so it is allowed as an identifier here.- Return type. The function declares
List<String>, a read-only view, and returns theMutableListheld insolutions. AnyMutableListis also aList. - Printing.
println(list)shows the elements without quotes:[((())), (()()), (())(), ()(()), ()()()].
Complexity
The number of well-formed strings is the n-th Catalan number: 1, 2, 5, 14, 42, 132, 429 and 1430 for n = 1 to 8. The search visits prefixes of valid strings, with a few extra dead ends cut by the two prunes, and each string costs O(n) to build. So the time is roughly proportional to the Catalan number times n, much less than 2^(2n). The recursion depth is 2n, and the stored output dominates the space.
Edge cases and common mistakes
- n = 1. The only result is
"()". - n = 2. The results are
"(())"and"()()", in that order, because'('is tried before')'. - Mixing up
n. Insidegenerate,nis the full length,2 * n, not the number of pairs. Passing the pair count would produce strings that are too short. - Checking only the counts at the end. Equal numbers of
'('and')'aren't enough:")("has equal counts. The checkopen < closedon every prefix is what rules it out. - Forgetting to reset
solutions. A second call would return the first call's strings as well. - Result order. This solution returns the strings in lexicographic order, with
'('before')'. The task allows any order, but it's useful to know it is stable between runs.
Testing
generateParentheses(1)returns["()"].generateParentheses(2)returns["(())", "()()"].generateParentheses(3)returns the five strings listed above.generateParentheses(4).sizeis 14, andgenerateParentheses(8).sizeis 1430.