Generate Parentheses

Problem Link

Generate Parentheses – LeetCode

Problem: Generate Parentheses

Problem Statement

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

Examples

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

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

Constraints

• 1 <= n <= 8

Intuition

We need to generate all valid combinations of n opening and n closing brackets.
A combination is valid if:

• At any point, the number of closing brackets used does not exceed the number of opening brackets used.

• At the end, we must use exactly n opening and n closing brackets.

This is a classic case for the Input-Output Method:

• Input: counts of opening and closing brackets left (open, close)

• Output: the current string built so far

Input-Output Recursive Method

Function Signature

void helper(int open, int close, String output, List<String> ans)

Parameters:

• open: Number of opening brackets left to place

• close: Number of closing brackets left to place

• output: Current valid string being built

• ans: List collecting all valid combinations

Base Case

If open == 0 and close == 0:

• We’ve placed all brackets correctly → add output to result.

Recursive Choices

1. If open > 0:

   • We can safely add "(" → helper(open - 1, close, output + "(", ans)

2. If close > open:

   • Only if we’ve already placed more opening brackets, we can add ")"
     → helper(open, close - 1, output + ")", ans)

Code (Java)

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

    private void helper(int open, int close, String output, List<String> ans) {
        // Base case
        if (open == 0 && close == 0) {
            ans.add(output);
            return;
        }

        // Choice 1: Add opening bracket
        if (open > 0) {
            helper(open - 1, close, output + "(", ans);
        }

        // Choice 2: Add closing bracket
        if (close > open) {
            helper(open, close - 1, output + ")", ans);
        }
    }
}

Time and Space Complexity

• Time Complexity: O(2^2n) in the worst case, but effectively closer to O(Catalan(n))

  • Number of valid combinations = nth Catalan number ≈ 4^n / (n√n)

• Space Complexity: O(n) for the recursion stack depth

  • 2n depth (maximum length of string), plus O(Catalan(n)) for result list

Dry Run

Input: n = 2

Start: open = 2, close = 2, output = ""

Step 1: Add "(" → open = 1, close = 2 → "("
Step 2: Add "(" → open = 0, close = 2 → "(("
Step 3: Add ")" → open = 0, close = 1 → "(()"
Step 4: Add ")" → open = 0, close = 0 → "(())" → valid

Backtrack

Step 2: Add ")" → open = 1, close = 1 → "()"  
Step 3: Add "(" → open = 0, close = 1 → "()("  
Step 4: Add ")" → open = 0, close = 0 → "()()" → valid

Output: ["(())", "()()"]

Conclusion

This problem is a classic example of the input-output recursion model, where decisions (include/exclude) are made based on constraints. The bracket generation logic is based on careful constraint checking and demonstrates the power of controlled recursive tree traversal.