59 / 75
Medium
Generate Parentheses
#59backtrackingstringrecursion
Backtrack to generate valid combinations: add '(' if open < n, add ')' if close < open.
Example:
Input:
n=3Output:
['((()))', '(()())', '(())()', '()(())', '()()()']Common Mistakes:
- Generating all permutations then filtering (too slow)
- Wrong condition for adding ')' (should be close < open)
- Not backtracking (forgetting to remove last character)
- Using String concatenation instead of StringBuilder
Notes:
Catalan number problem. Time O(4^n / √n), Space O(n) for recursion depth. Only generates valid combinations, doesn't waste time on invalid ones.
💻
Java Solution Hidden
Enable “Show Full Solution” to view the code
Backtrack to generate valid combinations: add '(' if open < n, add ')' if close < open.
Example:
Input:
n=3Output:
['((()))', '(()())', '(())()', '()(())', '()()()']Common Mistakes:
- Generating all permutations then filtering (too slow)
- Wrong condition for adding ')' (should be close < open)
- Not backtracking (forgetting to remove last character)
- Using String concatenation instead of StringBuilder
Notes:
Catalan number problem. Time O(4^n / √n), Space O(n) for recursion depth. Only generates valid combinations, doesn't waste time on invalid ones.
59/75
Generate Parentheses