Problem overview
The method generateParentheses receives an integer n, with 1 <= n <= 8, and returns every well-formed string made of n pairs of parentheses, as a [String]. A string is well-formed when every ( is closed by a later ), in the nested or side-by-side way you would write them in an expression.
For n = 1 the only answer is ["()"]. For n = 3 there are five: ["((()))", "(()())", "(())()", "()(())", "()()()"].
Approach: build the string one character at a time
Every answer has length 2 * n, and each position holds either ( or ). Trying all of those strings means 2^(2n) candidates, and most of them are not well-formed. Backtracking builds strings left to right and drops a partial string as soon as it can't lead to a valid one.
The state of a partial string current is two counters: open, the number of ( placed so far, and closed, the number of ). Two facts follow from the definition:
- A prefix with more
)than(can never be repaired, since a later character can't pair with a closing parenthesis that already came first. So whenopen < closed, stop. - At the end, the numbers of
(and)must be equal. Ifopenis already much larger thanclosed, the remaining positions can't supply enough closing parentheses. This is the second pruning rule.
From each surviving prefix, the search tries two extensions: append ( and append ). When the string reaches the target length, it is saved. Appending ( first means the answers come out in the order shown above, starting with ((())).
A short trace for n = 1, where the target length is 2: from "" the search tries "(" and ")". The string ")" has open = 0 and closed = 1, so it is dropped at once. From "(" it tries "((", which is dropped because two opens can't be closed in the remaining positions, and "()", which reaches full length with equal counts and is saved.
Step by step
- Add a property
solutionsof type[String]!abovegenerateParentheses. The helper appends to it, and it gets its value when the entry method runs. - Reset it at the top of
generateParenthesesby assigning an empty array, so results of earlier calls don't carry over. - Start the search with
generate("", 2 * n, 0, 0): an empty string, the target length, and zero for both counters. - Return
solutionsafter the search. - Declare
generateabove it, takingcurrent, the target lengthnand the countsopenandclosed, all unlabeled. - First prune: return if
open < closed. - Second prune: return if
open > closed + (n - current.count + 1). - Completion: if
current.count == n, appendcurrenttosolutionsand return. A full-length string that survived both prunes is balanced. - Extend twice: call
generatewithcurrent + "("andopen + 1, then withcurrent + ")"andclosed + 1.
The solution in Swift
class Solution {
func generate(_ current: String, _ n: Int, _ open: Int, _ closed: Int) {
if open < closed {
return
}
if open > closed + (n - current.count + 1) {
return
}
if current.count == n {
solutions.append(current)
return
}
generate(current + "(", n, open + 1, closed)
generate(current + ")", n, open, closed + 1)
}
var solutions: [String]!
func generateParentheses(_ n: Int) -> [String] {
solutions = []
generate("", 2 * n, 0, 0)
return solutions
}
}
The Swift details worth a closer look:
- The parameter
ningenerateis a length. It receives2 * nfrom the caller, so inside the helper it means the target length of the string, not the number of pairs. - Strings are values.
current + "("builds a new string, andcurrentitself is unchanged. That is why no undo step is needed here, unlike in the Sudoku or N Queens lessons: each recursive call gets its own string. String.countcounts characters. A Swift string can't be indexed by integer, andcountwalks the string to count its characters, so it costs time proportional to the length. The strings here are at most 16 characters long, so this is cheap.[String]!. The!declares an implicitly unwrapped optional. The property starts asniland is used like an ordinary array aftersolutions = []. Using it before assigning would stop the program. A plainvar solutions: [String] = []would avoid the optional, but the lesson shows this form.- Parameter names that are not keywords.
openis a contextual keyword in Swift (an access level used in frameworks), but it is allowed as a parameter name, so the code compiles as written. - String literals.
"("is aStringhere, socurrent + "("concatenates two strings.
Complexity
Time: about O(4^n / sqrt(n)), up to the length of each string. The number of well-formed strings is the Catalan number: 1, 2, 5, 14, ... and 1,430 for n = 8. The search visits somewhat more prefixes than that, because it only prunes when the counts show a prefix is hopeless, and every string takes O(n) to build and copy. For n up to 8 it finishes at once.
Space: O(n) for the recursion, plus the output. The stack is at most 2n calls deep, each holding a string of up to 2n characters. The result list holds all answers.
Edge cases and common mistakes
n = 1. The result is["()"].n = 2. The result is["(())", "()()"].- Counting only the totals. A string such as
")("has equal numbers of both characters but is not well-formed. The checkopen < closedon every prefix is what rejects it. - Not resetting
solutions. Calling the method twice on the sameSolutionobject would otherwise return the first call's strings as well. - Mixing up
n. Passingninstead of2 * ntogeneratewould stop strings at half the needed length. - The second prune and full-length strings. At full length, the numbers of
(and)add up to2n, so their difference is even. The prune allows a difference of at most 1, so only equal counts reach the completion check. That is why the lesson can treat every full-length survivor as balanced.
Testing
n = 1gives["()"].n = 2gives["(())", "()()"].n = 3gives["((()))", "(()())", "(())()", "()(())", "()()()"].n = 8gives 1,430 strings.
