← Back to Index

📚 Generate Parentheses – Java Cheat Sheet

📌 What Is It?

The Generate Parentheses problem involves generating all combinations of well-formed parentheses for a given number n.

🧱 Pattern Template

Recursive Backtracking

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

    private void backtrack(List<String> result, StringBuilder current, int open, int close, int max) {
        if (current.length() == max * 2) {
            result.add(current.toString());
            return;
        }

        if (open < max) {
            current.append("(");
            backtrack(result, current, open + 1, close, max);
            current.deleteCharAt(current.length() - 1); // Backtrack
        }
        if (close < open) {
            current.append(")");
            backtrack(result, current, open, close + 1, max);
            current.deleteCharAt(current.length() - 1); // Backtrack
        }
    }
}

▶️ View Animation

📊 Time Complexity

• Time Complexity: O(4^n / √n), where n is the number of pairs of parentheses. This is the Catalan number complexity.
• Space Complexity: O(n), for the recursion stack.

✅ Use Cases

• Generating all valid combinations of parentheses.
• Exploring all combinations of balanced strings.

📘 Common LeetCode Problems

• 22. Generate Parentheses [Medium] Backtracking

🧪 Example

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

Explanation:
- For n = 3, generate all valid combinations of 3 pairs of parentheses.

💡 Pro Tips

• Use two counters (open and close) to track the number of open and close parentheses used so far.
• Only add an open parenthesis if open < max.
• Only add a close parenthesis if close < open.
• Use backtracking to explore all valid combinations efficiently.