Problem overview
The function generate_parentheses takes n, the number of pairs, and returns a Vec<String> holding every well-formed string made of n pairs of parentheses. A string is well-formed when every ( is closed by a later ) and no ) appears without an open ( to match it.
For n = 1 the only answer is ["()"]. For n = 2 there are two, (()) and ()(). For n = 3 there are five: ((())), (()()), (())(), ()(()) and ()()(). The input is between 1 and 8.
Approach: build the string one character at a time
Every answer has exactly 2 * n characters, and each character is either ( or ). Trying all 2^(2n) strings and checking each one would work, but nearly all of them are invalid. It's better to build the string left to right and abandon a prefix the moment it can no longer become valid.
Two facts about a prefix decide that. Let open be the number of ( so far and closed the number of ).
- If
closedis larger thanopen, some)has no partner, and adding more characters can't fix it. - The surplus
open - closedis the number of parentheses still waiting to be closed. If that surplus is larger than the number of characters left to write, there is no room to close them all.
A prefix that passes both checks and has reached full length is therefore balanced: its surplus must be at most 0 and, from the first check, at least 0. Nothing else needs to be verified at the end.
Step by step
- Create the result vector
solutionswithlet mut, since the helper will push into it. - Start the recursion with
Self::gen: an emptyString, the full target length2 * n, both counters at 0 and a mutable borrow ofsolutions. - Return
solutionsas the final expression, which moves the vector back to the caller. - Declare
genwith the current string, the target length (namedninside the helper), the two counters and a&mut Vec<String>. It returns nothing. - Prune on unmatched
): return whenopen < closed. - Prune on too many
(: return whenopen > closed + (n - current.len() as i32). The parenthesised part is the number of characters still to write. - Collect complete strings. When
current.len() as i32 == n, pushcurrentintosolutionsand return. - Branch on
(. Clonecurrent, push'('onto the copy and recurse withopen + 1. - Branch on
). Movecurrentitself into a new variable, push')'and recurse withclosed + 1.
The solution in Rust
impl Solution {
fn generate_parentheses(n: i32) -> Vec<String> {
let mut solutions = Vec::new();
Self::gen(String::new(), 2 * n, 0, 0, &mut solutions);
solutions
}
fn gen(current: String, n: i32, open: i32, closed: i32, solutions: &mut Vec<String>) {
if open < closed {
return;
}
if open > closed + (n - current.len() as i32) {
return;
}
if current.len() as i32 == n {
solutions.push(current);
return;
}
let mut c_open = current.clone();
c_open.push('(');
Self::gen(c_open, n, open + 1, closed, solutions);
let mut c_closed = current;
c_closed.push(')');
Self::gen(c_closed, n, open, closed + 1, solutions);
}
}
The Rust details worth a closer look:
- Two meanings of
n. Ingenerate_parentheses,nis the number of pairs. The call passes2 * n, so insidegenthe parameter callednis the total length of the string. - Ownership of the string.
gentakescurrent: Stringby value, so each call owns its prefix. The first branch needs the prefix again for the second branch, so it works on aclone(). The second branch is the last use, so it takescurrentitself, with no copy. - Casting the length.
len()returns ausizeandnis ani32. Rust never mixes integer types implicitly, so the code writescurrent.len() as i32. For these short strings the cast can't lose information. - Bytes versus characters.
len()counts bytes. Here every character is ASCII, so bytes and characters agree. - Pushing into the vector.
solutions.push(current)moves the string into the vector, which is fine because the function returns right afterwards. The parametersolutionsis already a&mut Vec<String>, so the recursive calls pass it on as it is. - Inferred element type.
Vec::new()ingenerate_parentheseshas no annotation. The compiler infersVec<String>from the return type.
Complexity
The number of well-formed strings with n pairs is the Catalan number: 1, 2, 5, 14, ... and 1430 for n = 8. It grows roughly like 4^n divided by a power of n.
Time. The pruning guarantees that every call that continues past the two checks is a prefix of some valid answer, so the search never wanders far into dead ends. The work is proportional to the number of such prefixes times the cost of copying a string of up to 2n characters. The output alone takes O(n) per string, so the total grows with the Catalan number times a polynomial in n.
Space beyond the output. The recursion is at most 2n calls deep, and each live call can hold a string of up to 2n characters, so about O(n^2).
Edge cases and common mistakes
- Only checking at the end. Generating all
2^(2n)strings and filtering them works but does far more work than the pruned search. - Allowing
closed > open. Without the first check the program produces strings such as())(. - Skipping the second check. The prefix
((forn = 1fits the first rule, but it can't be closed within two characters. Without the second prune such prefixes keep growing until the length check, and complete-looking but unbalanced strings reach the result. - Reusing a moved string. Once
currentis moved intoc_closed, using it again is a compile error. That's why the clone comes first.
Testing
n = 1gives["()"].n = 2gives["(())", "()()"].n = 3gives["((()))", "(()())", "(())()", "()(())", "()()()"].n = 8gives 1430 strings.
