Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Example 1:

Input: n = 3
Output: [”((()))”,”(()())”,”(())()”,”()(())”,”()()()”]

Example 2:

Input: n = 1
Output: [”()”]

Constraints:

• 1 <= n <= 8

Approach - backtrack

• We build the string step-by-step, choosing between ’(’ and ’)’, making sure:
  • We never add more ) than (
  • We don’t add more than n ( or )
• Time: O(2ⁿ * n)
  In the worst case, each level has 2 choices (add ( or )), so 2ⁿ total combinations.
  Each string is of length 2n → copying takes O(n)
  But due to constraints, actual valid calls ≈ Catalan number C(n) = O(4ⁿ / n
• Space: O(n) recursion depth + output list.

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> para = new ArrayList<>();
        backtrack(para,"",0,0,n);
        return para;
    }
 
    public void backtrack(List<String> para, String curr, int open, int close, int max) {
        if (curr.length() == 2*max) {
            para.add(curr);
            return;
        }
 
        if (open < max) {
            backtrack(para, curr + "(", open + 1, close, max);
        }
 
        if (close < open) {
            backtrack(para, curr + ")", open, close + 1, max);
        }
    }
}