Generate Parentheses
Generate Parentheses is a medium recursion & backtracking problem solved with the pick / not-pick pattern.
The best approach, optimal (backtracking with open and close counts), runs in O(Cn · n), where Cn is the n-th Catalan number time and O(n) besides the output space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (all bracket strings, filter the balanced ones) up.
Problem
Given an integer n, return every string made of n opening brackets ( and n closing brackets ) that is balanced: each ) closes an earlier unmatched (, and nothing is left open at the end.
Each balanced string must appear exactly once; the order of the list does not matter.
Examples
Example 1
- Input
n = 2- Output
["(())", "()()"]- Why
- With two pairs there are exactly two balanced strings.
Example 2
- Input
n = 1- Output
["()"]- Why
- One pair can only be written one way.
Example 3
- Input
n = 3- Output
["((()))", "(()())", "(())()", "()(())", "()()()"]- Why
- Five balanced strings; any order is accepted.
Constraints
1 <= n <= 8- The strings may be returned in any order.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 5 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (all bracket strings, filter the balanced ones) | O(2^(2n) · n) | O(n) besides the output |
| Optimal (backtracking with open and close counts) | O(Cn · n), where Cn is the n-th Catalan number | O(n) besides the output |
1Brute force (all bracket strings, filter the balanced ones)
O(2^(2n) · n)There are 4^n strings and each check costs O(n).O(n) besides the outputThe recursion depth and the current string are O(n).Generate every string of length 2n made of '(' and ')', and keep the ones that are balanced: scanning left to right, the count of unmatched '(' never goes negative and ends at zero.
- Recursively build all 2^(2n) strings.
- For each complete string, scan it with a balance counter.
- Keep it if the balance never drops below 0 and ends at 0.
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
build(new char[2 * n], 0, res);
return res;
}
private void build(char[] cur, int pos, List<String> res) {
if (pos == cur.length) {
if (valid(cur)) res.add(new String(cur));
return;
}
cur[pos] = '(';
build(cur, pos + 1, res);
cur[pos] = ')';
build(cur, pos + 1, res);
}
private boolean valid(char[] s) {
int bal = 0;
for (char c : s) {
bal += c == '(' ? 1 : -1;
if (bal < 0) return false;
}
return bal == 0;
}
}class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = []
cur = []
def valid() -> bool:
bal = 0
for c in cur:
bal += 1 if c == "(" else -1
if bal < 0:
return False
return bal == 0
def build() -> None:
if len(cur) == 2 * n:
if valid():
res.append("".join(cur))
return
for c in "()":
cur.append(c)
build()
cur.pop()
build()
return resclass Solution {
bool valid(const string& s) {
int bal = 0;
for (char c : s) {
bal += c == '(' ? 1 : -1;
if (bal < 0) return false;
}
return bal == 0;
}
void build(string& cur, int len, vector<string>& res) {
if ((int)cur.size() == len) {
if (valid(cur)) res.push_back(cur);
return;
}
for (char c : {'(', ')'}) {
cur.push_back(c);
build(cur, len, res);
cur.pop_back();
}
}
public:
vector<string> generateParenthesis(int n) {
vector<string> res;
string cur;
build(cur, 2 * n, res);
return res;
}
};function generateParenthesis(n) {
const res = [];
const cur = [];
const valid = () => {
let bal = 0;
for (const c of cur) {
bal += c === '(' ? 1 : -1;
if (bal < 0) return false;
}
return bal === 0;
};
const build = () => {
if (cur.length === 2 * n) {
if (valid()) res.push(cur.join(''));
return;
}
for (const c of ['(', ')']) {
cur.push(c);
build();
cur.pop();
}
};
build();
return res;
}2Optimal (backtracking with open and close counts)
O(Cn · n), where Cn is the n-th Catalan numberEvery leaf is one of the Cn valid strings, and building or copying each costs O(n).O(n) besides the outputThe recursion depth is 2n.Build the string one bracket at a time and only make moves that keep it valid. An opening bracket is allowed while fewer than n have been used. A closing bracket is allowed only while it matches an earlier unmatched opening bracket (close < open). Every branch then ends in a valid string, so nothing is wasted.
- Recurse with (current string, open, close).
- If the length is 2n, record the string.
- If open < n, add '(' and recurse. If close < open, add ')' and recurse.
class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
backtrack(new StringBuilder(), 0, 0, n, res);
return res;
}
private void backtrack(StringBuilder sb, int open, int close, int n, List<String> res) {
if (sb.length() == 2 * n) {
res.add(sb.toString());
return;
}
if (open < n) {
sb.append('(');
backtrack(sb, open + 1, close, n, res);
sb.deleteCharAt(sb.length() - 1);
}
if (close < open) {
sb.append(')');
backtrack(sb, open, close + 1, n, res);
sb.deleteCharAt(sb.length() - 1);
}
}
}class Solution:
def generateParenthesis(self, n: int) -> List[str]:
res = []
cur = []
def backtrack(open_: int, close: int) -> None:
if len(cur) == 2 * n:
res.append("".join(cur))
return
if open_ < n:
cur.append("(")
backtrack(open_ + 1, close)
cur.pop()
if close < open_:
cur.append(")")
backtrack(open_, close + 1)
cur.pop()
backtrack(0, 0)
return resclass Solution {
void backtrack(string& cur, int open, int close, int n, vector<string>& res) {
if ((int)cur.size() == 2 * n) {
res.push_back(cur);
return;
}
if (open < n) {
cur.push_back('(');
backtrack(cur, open + 1, close, n, res);
cur.pop_back();
}
if (close < open) {
cur.push_back(')');
backtrack(cur, open, close + 1, n, res);
cur.pop_back();
}
}
public:
vector<string> generateParenthesis(int n) {
vector<string> res;
string cur;
backtrack(cur, 0, 0, n, res);
return res;
}
};function generateParenthesis(n) {
const res = [];
const cur = [];
const backtrack = (open, close) => {
if (cur.length === 2 * n) {
res.push(cur.join(''));
return;
}
if (open < n) {
cur.push('(');
backtrack(open + 1, close);
cur.pop();
}
if (close < open) {
cur.push(')');
backtrack(open, close + 1);
cur.pop();
}
};
backtrack(0, 0);
return res;
}Edge cases to test
- n = 1
- The largest n, where the answer has 1430 strings
- Strings that close early, like ()()(), and strings that nest fully, like ((()))
Hints
Hint 1
You could generate every string of 2n brackets and keep the balanced ones. How many of those are wasted?
Hint 2
Build the string left to right. When is it allowed to add '('? When is it allowed to add ')'?
Hint 3
Add '(' while fewer than n are open in total; add ')' only while it would close an unmatched '('. Every completed string is then valid.
FAQ
What is the best time complexity for Generate Parentheses?
Optimal (backtracking with open and close counts) runs in O(Cn · n), where Cn is the n-th Catalan number time and O(n) besides the output extra space. Every leaf is one of the Cn valid strings, and building or copying each costs O(n).
Which pattern does Generate Parentheses use?
It is a recursion & backtracking problem that uses the pick / not-pick pattern. Other problems with the same pattern: Generate all binary strings without consecutive 1's, Subsets (2 choices per element), Subsets II.
Is there a brute force solution for Generate Parentheses?
Yes. Brute force (all bracket strings, filter the balanced ones) takes O(2^(2n) · n) time and O(n) besides the output space. Generate every string of length 2n made of '(' and ')', and keep the ones that are balanced: scanning left to right, the count of unmatched '(' never goes negative and ends at zero.
Which edge cases should I test for Generate Parentheses?
n = 1; The largest n, where the answer has 1430 strings; Strings that close early, like ()()(), and strings that nest fully, like ((())).