Generate Parentheses Editorial

Practice Problem Link: Generate Parentheses

Please make sure to try solving the problem yourself before looking at the editorial.

Problem Statement

Given a number n denoting n pairs of parentheses, return all valid expressions using the n pairs of parentheses.

Naive Approach

In the naive approach, we can generate all the possible strings with n ‘(’ and n ‘)’ and check if each of them is valid. If they are valid, we can store them in a list.

Analysis

• Time Complexity: O(4ⁿ * n)
• Space Complexity: O(4ⁿ * n)

Optimal Approach

To enumerate this problem, we will try to represent it as a sum of disjoint subsets, so that it is easier to count. Let us define a property of a valid parenthesis sequence as "closure number" as the least index >= 0 so that S[0], S[1], ..., S[2*index+1] is valid. Since every parenthesis sequence has a unique closure number, we can enumerate them individually. Refer to the implementation for better understanding.

Analysis

• Time Complexity: O(n * nth Catalan Number))
• Space Complexity: O(n * nth Catalan Number))

Implementation

C++

vector<string> generateParentheses(int n) {
    vector<string> result;
	if(n == 0) {
		string empty = "";
		result.push_back(empty);
	}
	else {
		for(int closure = 0; closure < n; closure++) {
			for(auto left: generateParentheses(closure)) {
				for(auto right: generateParentheses(n - closure - 1)) {
					result.push_back("(" + left + ")" + right);
				}
			}
		}
	}
	return result;
}

Java

class Solution {
	List<String> generateParentheses(int n) {
	    List<String> result = new ArrayList<>();
        if (n == 0) {
			String empty = "";
            result.add(empty);
        } 
		else {
            for (int closure = 0; closure < n; closure++)
                for (String left: generateParentheses(closure))
                    for (String right: generateParentheses(n - closure - 1))
                        result.add("(" + left + ")" + right);
        }
        return result;
	}
}