LeetCode Solutions Blog

Generate Parentheses

Number: 22

Difficulty: Medium

Paid? No

Problem Description

Given n pairs of parentheses, the task is to generate all combinations of well-formed (i.e. valid) parentheses.

Key Insights

Use a backtracking approach to build the valid combinations step by step.
At any recursion step, you can add an opening parenthesis if you still have one available.
You can add a closing parenthesis only if it would not result in an invalid sequence (i.e., the number of closing parentheses is less than the number of opening ones).
The solution leverages recursion to explore all potential valid sequences while pruning invalid paths early.

Space and Time Complexity

Time Complexity: O(4^n / (n^(3/2))) Space Complexity: O(n) for the recursion stack, plus space for storing all valid combinations.

Solution

The solution uses a recursive backtracking technique to generate the combinations. The algorithm maintains counters for the number of '(' and ')' added to the current string. It recursively adds a '(' if the count is less than n and adds a ')' if doing so does not make the string invalid (i.e., if the count of ')' is less than the count of '('). When a valid combination reaches a length of 2*n, it is added to the result list.

Code Solutions

def generateParenthesis(n):
    # List to store valid combinations
    result = []
    
    # Helper function for backtracking
    def backtrack(current, open_count, close_count):
        # If current string reaches the maximum length, it's a valid combination
        if len(current) == 2 * n:
            result.append(current)
            return
        # If we can add an opening parenthesis, do it
        if open_count < n:
            backtrack(current + '(', open_count + 1, close_count)
        # If adding a closing parenthesis maintains the validity, do it
        if close_count < open_count:
            backtrack(current + ')', open_count, close_count + 1)
    
    # Start the recursion with an empty string and zero counts for both
    backtrack("", 0, 0)
    return result

# Example usage:
print(generateParenthesis(3))