How do you generate all valid combinations of n pairs of parentheses?
Build the string character by character. You may add an opening bracket while fewer than n have been used, and a closing bracket only when it would not exceed the number of openings. A string of length 2n is valid.
Explain it simply
A valid bracket string never closes something that was not opened. So while building, keep two counters: how many "(" and how many ")" you have used.
Two rules are enough: you can add "(" if you have used fewer than n; you can add ")" if the closes so far are fewer than the opens. These rules prevent invalid strings from ever being built, so you do not need to check them afterwards.
Example
function generateParenthesis(n) {
const result = [];
function build(current, open, close) {
if (current.length === 2 * n) {
result.push(current);
return;
}
if (open < n) build(current + "(", open + 1, close);
if (close < open) build(current + ")", open, close + 1);
}
build("", 0, 0);
return result;
}
console.log(generateParenthesis(3));
// Output: ["((()))","(()())","(())()","()(())","()()()"]Complexity
Time about O(4^n / sqrt(n)) (Catalan number of results), space O(n) for recursion.
What to say in the interview
"I build the string with two counters. I can add an open bracket while open is less than n, and a close bracket while close is less than open. That only produces valid strings, and the number of results is the nth Catalan number, so time is roughly O(4^n / sqrt(n))."
Common mistakes
- Generating all 2^(2n) strings and filtering, which is much slower.
- Allowing a close bracket when close equals open.