LeetCode 22: Generate Parentheses Solution in Python Explained

Problem Statement

LeetCode 22, Generate Parentheses, is a medium-level challenge where you’re given an integer n and need to generate all possible combinations of n pairs of well-formed parentheses. A combination is well-formed if every opening parenthesis '(' has a matching closing parenthesis ')', and the string is properly nested. Return these combinations as a list of strings.

Constraints

1 <= n <= 8: Number of pairs ranges from 1 to 8.

Example

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]
Explanation: Five valid ways to arrange 3 pairs of parentheses.

Input: n = 1
Output: ["()"]
Explanation: One pair gives one combination.

Input: n = 2
Output: ["(())","()()"]
Explanation: Two valid arrangements for 2 pairs.

Understanding the Problem

How do you solve LeetCode 22: Generate Parentheses in Python? Imagine generating all valid ways to arrange 3 pairs of parentheses, like "((()))" or "()()()". Each combination must have exactly n opening '(' and n closing ')', and at every point, the number of closing brackets must not exceed the number of opening ones (e.g., ")(" is invalid). This is a combinatorial problem, and we’ll explore two solutions: a Backtracking approach (efficient) and a Brute Force approach (simpler but slower).

Solution 1: Backtracking (Primary)

Explanation

Use backtracking to build valid combinations by adding '(' or ')' one at a time, ensuring at each step that the string remains valid. Track the number of open and close brackets left to use, only adding a ')' if there are more open brackets than closed ones.

Here’s a visual for n = 2:

Start: "", open=2, close=2
Add '(': "(", open=1, close=2
Add '(': "((", open=0, close=2
Add ')': "(()", open=0, close=1
Add ')': "(())", open=0, close=0 (done)
Backtrack: "(", add ')': "()", open=1, close=1 (done)

Initialize Result.

Start with an empty list to store combinations.

Define Backtracking Function.

Takes current string, open brackets left, close brackets left.

Base Case.

If no open or close brackets remain, add the string to results.

Add Brackets.

Add '(' if open brackets remain.
Add ')' if more close brackets than open are available.

Return Result.

Return the list of all valid combinations.

Step-by-Step Example

Example 1: n = 2

We have n = 2 and want all valid combinations.

Goal: Generate all 2-pair parentheses combinations.
Result for Reference: ["(())", "()()"].
Start: Result list empty, call backtrack("", 2, 2).
Step 1: backtrack("", 2, 2).

Open > 0, add '(' → backtrack("(", 1, 2).

Step 2: backtrack("(", 1, 2).

Open > 0, add '(' → backtrack("((", 0, 2).
Close > open (2 > 1), add ')' → backtrack("()", 1, 1).

Step 3: backtrack("((", 0, 2).

Open = 0, skip '('.
Close > open (2 > 0), add ')' → backtrack("(()", 0, 1).

Step 4: backtrack("(()", 0, 1).

Close > open (1 > 0), add ')' → backtrack("(())", 0, 0).

Step 5: backtrack("(())", 0, 0).

Open = close = 0, add "(())" to result.
Result: ["(())"].

Step 6: Backtrack to "()", backtrack("()", 1, 1).

Open > 0, add '(' → backtrack("(()", 0, 1) (already done).
Close > open (1 > 0), add ')' → backtrack("()()", 1, 0).

Step 7: backtrack("()()", 1, 0).

Open > 0, add '(' → backtrack("()(()", 0, 0).
Close = open (0 = 0), skip ')'.

Step 8: backtrack("()(()", 0, 0).

Open = close = 0, add "()()" to result.
Result: ["(())", "()()"].

Finish: Return ["(())", "()()"].

Example 2: n = 1

Now, n = 1.

Goal: Generate 1-pair combinations.
Result for Reference: ["()"].
Start: Result empty, backtrack("", 1, 1).
Step 1: backtrack("", 1, 1).

Add '(' → backtrack("(", 0, 1).

Step 2: backtrack("(", 0, 1).

Close > open (1 > 0), add ')' → backtrack("()", 0, 0).

Step 3: backtrack("()", 0, 0).

Add "()" to result.
Result: ["()"].

Finish: Return ["()"].

How the Code Works (Backtracking)

Here’s the Python code with line-by-line explanation:

def generateParenthesis(n: int) -> list[str]:
    # Line 1: Initialize result list to store combinations
    result = []

    # Line 2: Define backtracking helper function
    def backtrack(current: str, open_count: int, close_count: int) -> None:
        # Line 3: Base case - if no brackets left, add to result
        if open_count == 0 and close_count == 0:
            # Line 4: Append current combination to result
            result.append(current)
            # Line 5: Return to backtrack
            return

        # Line 6: If open brackets remain, add '('
        if open_count > 0:
            # Line 7: Recursively call with '(' added, reduce open_count
            backtrack(current + "(", open_count - 1, close_count)

        # Line 8: If more close than open, add ')'
        if close_count > open_count:
            # Line 9: Recursively call with ')' added, reduce close_count
            backtrack(current + ")", open_count, close_count - 1)

    # Line 10: Start backtracking with empty string and n pairs
    backtrack("", n, n)
    # Line 11: Return all combinations
    return result

Alternative: Brute Force with Validation

Explanation

Generate all possible sequences of 2n brackets (n '(' and n ')'), then filter for valid ones using a stack-like check. It’s less efficient but shows a different perspective.

Generate Sequences.

Create all combinations of n '(' and n ')'.

Validate Each.

Use a counter to check if each sequence is well-formed.

Return Valid Ones.

Return list of valid sequences.

Step-by-Step Example (Brute Force)

For n = 2:

Goal: Generate valid 2-pair combinations.
Result for Reference: ["(())", "()()"].
Start: Result empty.
Step 1: Generate sequences (2 '(' and 2 ')').

Possible: ["()()", "(())", "())(", ")()(", "))((", "(()(", "((())", "(())", ")((", "()(()"].

Step 2: Validate each.

"()()": Counter: 1,0,1,0 → Valid.
"(())": 1,2,1,0 → Valid.
"())(": 1,0,1,0 (invalid order) → Invalid.
")()(": -1 (invalid) → Invalid.
"))((": -1 → Invalid.
Others similarly invalid.

Finish: Result: ["(())", "()()"].

Code (Brute Force)

Here’s the brute force code with explanations:

def generateParenthesisBrute(n: int) -> list[str]:
    # Line 1: Function to check if a string is valid
    def is_valid(s: str) -> bool:
        # Line 2: Initialize counter for open brackets
        count = 0
        # Line 3: Scan each character
        for char in s:
            # Line 4: Increment for opening
            if char == '(':
                count += 1
            # Line 5: Decrement for closing, check if negative
            else:
                count -= 1
                if count < 0:
                    return False
        # Line 6: Valid if counter is 0
        return count == 0

    # Line 7: Generate all sequences recursively
    def generate_all(curr: str, open_remain: int, close_remain: int) -> None:
        # Line 8: Base case - if length matches 2n
        if len(curr) == 2 * n:
            # Line 9: Check validity and add if true
            if is_valid(curr):
                result.append(curr)
            return
        # Line 10: Add '(' if open brackets remain
        if open_remain > 0:
            generate_all(curr + "(", open_remain - 1, close_remain)
        # Line 11: Add ')' if close brackets remain
        if close_remain > 0:
            generate_all(curr + ")", open_remain, close_remain - 1)

    # Line 12: Initialize result list
    result = []
    # Line 13: Start generation with n open and n close
    generate_all("", n, n)
    # Line 14: Return valid combinations
    return result

Complexity

Backtracking:

Time: O(4^n / √n) – Catalan number of valid combinations, each built in O(n).
Space: O(n) – Recursion stack depth.

Brute Force:

Time: O(2^(2n) * n) – Generate 2^(2n) sequences, O(n) validation each.
Space: O(2^(2n)) – Store all sequences.

Efficiency Notes

Backtracking is far more efficient, generating only valid combinations (Catalan number), while brute force generates all 2^(2n) sequences and filters, making it impractical for larger n.

Key Insights

Tips to master LeetCode 22:

Balance is Key: Track open vs. close counts to stay valid—don’t let close exceed open.
Backtrack Smart: Only add brackets when rules allow—prune early!
Catalan Counts: Valid combinations follow the Catalan sequence, not all possibilities.

Additional Example

For n = 1:

Goal: Generate combinations.
Reference: ["()"].
Backtracking: "" → "(" → "()", done.
Result: ["()"].

Edge Cases

Min: n = 1 – Returns ["()"].
Max: n = 8 – Returns 429 combinations (Catalan number).
Single Type: n = 1 – Single valid "()".

Final Thoughts

Backtracking is the optimal way to solve LeetCode 22 in Python, efficient and clear. Check LeetCode 20: Valid Parentheses for more bracket fun!