Back to Stack
Medium
Generate Parentheses
Given `n` pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
Examples
Input:n = 3
Output:["((()))","(()())","(())()","()(())","()()()"]
Input:n = 1
Output:["()"]
Constraints
1 <= n <= 8
Backtracking (Implicit Stack)
Approach
Use recursion to build combinations. We can only add an open parenthesis if the number of open parentheses we have added so far is less than `n`. We can only add a close parenthesis if the number of close parentheses is less than the number of open parentheses. When the combination string length reaches `2 * n`, we have a valid combination and add it to our result list.
Complexity Analysis
Time Complexity
O(4^n / sqrt(n))
Space Complexity
O(n)
The time complexity corresponds to the n-th Catalan number. Space complexity is O(n) for the recursion call stack (or explicit stack list in Python).
Solution.java
class Solution { 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 currentString, int openCount, int closeCount, int max) { // Base case: combination is complete if (currentString.length() == max * 2) { result.add(currentString); return; } // Add open parenthesis if we haven't reached the limit if (openCount < max) { backtrack(result, currentString + "(", openCount + 1, closeCount, max); } // Add close parenthesis if there are unmatched open parentheses if (closeCount < openCount) { backtrack(result, currentString + ")", openCount, closeCount + 1, max); } }}