Problem
Given n pairs of parentheses, generate all combinations of well-formed parentheses.
Example
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]Solution
Backtracking. Add ( if open count < n. Add ) if close count < open count.
def generate_parenthesis(n):
result = []
def backtrack(s, open_n, close_n):
if len(s) == 2 * n:
result.append(s)
return
if open_n < n:
backtrack(s + '(', open_n + 1, close_n)
if close_n < open_n:
backtrack(s + ')', open_n, close_n + 1)
backtrack('', 0, 0)
return resultfunction generateParenthesis(n) {
const result = [];
function backtrack(s, openN, closeN) {
if (s.length === 2 * n) { result.push(s); return; }
if (openN < n) backtrack(s + '(', openN + 1, closeN);
if (closeN < openN) backtrack(s + ')', openN, closeN + 1);
}
backtrack('', 0, 0);
return result;
}void backtrack(vector<string>& result, string s, int openN, int closeN, int n) {
if (s.size() == 2 * n) { result.push_back(s); return; }
if (openN < n) backtrack(result, s + '(', openN + 1, closeN, n);
if (closeN < openN) backtrack(result, s + ')', openN, closeN + 1, n);
}
vector<string> generateParenthesis(int n) {
vector<string> result;
backtrack(result, "", 0, 0, n);
return result;
}public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
backtrack(result, "", 0, 0, n);
return result;
}
private void backtrack(List<String> result, String s, int openN, int closeN, int n) {
if (s.length() == 2 * n) { result.add(s); return; }
if (openN < n) backtrack(result, s + "(", openN + 1, closeN, n);
if (closeN < openN) backtrack(result, s + ")", openN, closeN + 1, n);
}Complexity
- Time: O(4ⁿ / √n)
- Space: O(4ⁿ / √n)
Explanation
The branching is constrained: only valid prefixes are explored. The count of solutions follows the Catalan number sequence.
Comments
Join the discussion. Got a question, found an issue, or want to share your experience?