LeetCode Problem

Problem Description

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

Examples

Input: 3
Output: ((())),(()()),(())(),()(()),()()()

Input: 1
Output: ()

Constraints

1 <= n <= 8

Follow-up

Approach to Solve

We use a backtracking algorithm to generate all valid combinations of parentheses. The key idea is to maintain the count of open and closed parentheses as we build each combination. We start with an empty string and recursively add open and closed parentheses, ensuring that:

We never add more than n open parentheses.
We only add a closing parenthesis if there are more open parentheses than closed ones.
We stop and add the combination to our result when the string length reaches 2n (n pairs of parentheses).

Code Implementation

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        def backtrack(s, left, right):
            if len(s) == 2 * n:
                result.append(s)
                return
            if left < n:
                backtrack(s + '(', left + 1, right)
            if right < left:
                backtrack(s + ')', left, right + 1)
        result = []
        backtrack('', 0, 0)
        return result

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> result = new ArrayList<>();
        backtrack(result, "", 0, 0, n);
        return result;
    }
    private void backtrack(List<String> result, String s, int left, int right, int n) {
        if (s.length() == 2 * n) {
            result.add(s);
            return;
        }
        if (left < n) backtrack(result, s + '(', left + 1, right, n);
        if (right < left) backtrack(result, s + ')', left, right + 1, n);
    }

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> result;
        backtrack(result, "", 0, 0, n);
        return result;
    }
    void backtrack(vector<string>& result, string s, int left, int right, int n) {
        if (s.length() == 2 * n) {
            result.push_back(s);
            return;
        }
        if (left < n) backtrack(result, s + '(', left + 1, right, n);
        if (right < left) backtrack(result, s + ')', left, right + 1, n);
    }

Explanation

The backtracking algorithm works as follows:

We start with an empty string and two counters: 'left' for open parentheses and 'right' for closed parentheses.
At each step, we have two choices: a. Add an open parenthesis '(' if we haven't used all n open parentheses yet. b. Add a closing parenthesis ')' if there are more open parentheses than closed ones.
We recursively explore these choices, building up the string as we go.
When the string length reaches 2n, we've used all parentheses, so we add this valid combination to our result.
The recursion naturally backtracks when it reaches the base case or when no more choices are available.

This approach ensures that all generated combinations are valid because:

We never close more parentheses than we've opened.
We never open more than n parentheses.
Every combination has exactly n open and n closed parentheses.

The time complexity is O(4^n / sqrt(n)) because the number of valid parentheses combinations is the nth Catalan number, which is approximately 4^n / (n^(3/2) * sqrt(pi)). The space complexity is O(n) due to the recursion depth and the space needed to store each combination.

Complexity

Time Complexity: O(4^n / sqrt(n))
Space Complexity: O(n)

LeetSolved

Generate Parentheses