Given an integer n, return all strings made of exactly n pairs of parentheses that are well formed (every opening bracket is closed in the right order). The strings may be returned in any order.
Example 1
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Example 2
Input: n = 1
Output: ["()"]
Constraints
- 1 <= n <= 8
Hints
Frequently asked at: Google, Amazon, Microsoft, Meta
Give it a real try first. Even 15 minutes of struggle makes the solution stick far better.
Intuition
The brute force builds every string of length 2n from ( and ) and checks each one, which is O(2^(2n) * n). A prefix can only become a valid answer if it never has more ) than ( and never uses more than n of (. If we only ever extend prefixes that satisfy these two rules, every leaf we reach is a valid answer and no time is spent on dead ends.
Algorithm
- Define
backtrack(path, open, close). - If
len(path) == 2n, record it. - If
open < n, add(and recurse withopen + 1. - If
close < open, add)and recurse withclose + 1.
Time:
O(4^n / sqrt(n)) (the Catalan number of answers, each of length 2n)Space: O(n) recursion depth, excluding the outputInterview tip: Interviewers often ask how many answers there are: it is the n-th Catalan number (1, 2, 5, 14, 42, ...), which explains the time complexity.
class Solution: def generateParenthesis(self, n: int) -> List[str]: res, path = [], []Β def backtrack(open_, close): if len(path) == 2 * n: res.append("".join(path)) return if open_ < n: # we can still open a bracket path.append("(") backtrack(open_ + 1, close) path.pop() if close < open_: # only close what is open path.append(")") backtrack(open_, close + 1) path.pop()Β backtrack(0, 0) return resCtrl + Enter runs the examples