Algorithm Day60 - Generate Parentheses (lc-22)

Posted on Edited on In , Views:

🧩 Problem Description

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

💬 Example

1
2
Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
1
2
Input: n = 1
Output: ["()"]

💡 Approach: Backtracking

We need to ensure:

  • We never place ')' unless there is a matching '(' available.
  • The number of '(' used cannot exceed n.
  • The number of ')' cannot exceed the number of '(' at any point.

So the recursive function tracks:

  • open: how many '(' have been used.
  • close: how many ')' have been used.

Valid recursion continues while open <= n and close <= open.

🔢 Java Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        backtrack(res, "", 0, 0, n);
        return res;
    }

    private void backtrack(List<String> res, String cur, int open, int close, int max) {
        if (cur.length() == max * 2) {
            res.add(cur);
            return;
        }
        if (open < max) {
            backtrack(res, cur + "(", open + 1, close, max);
        }
        if (close < open) {
            backtrack(res, cur + ")", open, close + 1, max);
        }
    }
}

⏱ Complexity Analysis

  • Time: O(4^n / √n), which is the Catalan number count.
  • Space: O(n) recursion depth + output size.

✍️ Summary

  • Classic backtracking problem generating balanced parentheses.
  • Use counts of open and close to ensure validity.
  • Total solutions = nth Catalan number.

Related problems:

  • lc-301 — Remove Invalid Parentheses
  • lc-856 — Score of Parentheses
  • lc-678 — Valid Parenthesis String