Generate Parentheses

MEDIUM

Description

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

Example 1:

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

Example 2:

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

Constraints:

1 <= n <= 8

Approaches

Checkout 3 different approaches to solve Generate Parentheses. Click on different approaches to view the approach and algorithm in detail.

Brute Force

This approach involves generating every possible sequence of length 2n using n opening and n closing parentheses. After generating a sequence, it is checked for well-formedness. If it's valid, it's added to the list of results.

Algorithm

Create a recursive function, say generateAll(char[] current, int pos, List<String> result).
The function will try to place either a ( or a ) at each position pos of a character array current of size 2*n.
The recursion proceeds from pos = 0 to 2*n - 1.
Base Case: When pos reaches 2*n, the character array is full. At this point, a validation function isValid(current) is called.
The isValid function checks two conditions:
1. The total count of ( equals the total count of ).
2. At no point during a left-to-right scan does the count of ) exceed the count of (.
If isValid returns true, the string representation of the current array is added to the final result list.

The brute-force method is the most straightforward way to approach the problem. We generate all possible strings of length 2n that can be formed using the characters ( and ). This results in 2^(2n) possible strings. For each generated string, we then perform a check to see if it's a valid, well-formed parenthesis string. A string is considered valid if it contains an equal number of opening and closing parentheses and if, at any point from left to right, the count of closing parentheses never exceeds the count of opening parentheses. While simple to understand, this method is highly inefficient because it explores a vast number of invalid combinations.

class Solution {
    public List<String> generateParenthesis(int n) {
        List<String> combinations = new ArrayList<>();
        generateAll(new char[2 * n], 0, combinations);
        return combinations;
    }

    private void generateAll(char[] current, int pos, List<String> result) {
        if (pos == current.length) {
            if (isValid(current)) {
                result.add(new String(current));
            }
        } else {
            current[pos] = '(';
            generateAll(current, pos + 1, result);
            current[pos] = ')';
            generateAll(current, pos + 1, result);
        }
    }

    private boolean isValid(char[] current) {
        int balance = 0;
        for (char c: current) {
            if (c == '(') {
                balance++;
            } else {
                balance--;
            }
            if (balance < 0) {
                return false;
            }
        }
        return (balance == 0);
    }
}

Complexity Analysis

Time Complexity: O(n * 2^(2n))Space Complexity: O(n)

Pros and Cons

Pros:

Simple to conceptualize and implement.

Cons:

Extremely inefficient due to its exponential time complexity.
Generates a massive number of invalid combinations that are later discarded.
Will likely result in a 'Time Limit Exceeded' error for n greater than a small value.

Code Solutions

Checking out 5 solutions in different languages for Generate Parentheses. Click on different languages to view the code.

public class Solution {
    private List < string > ans = new List < string > ();
    private int n;
    public List < string > GenerateParenthesis(int n) {
        this.n = n;
        Dfs(0, 0, "");
        return ans;
    }
    private void Dfs(int l, int r, string t) {
        if (l > n || r > n || l < r) {
            return;
        }
        if (l == n && r == n) {
            ans.Add(t);
            return;
        }
        Dfs(l + 1, r, t + "(");
        Dfs(l, r + 1, t + ")");
    }
}

Video Solution

Watch the video walkthrough for Generate Parentheses

Patterns:

Dynamic ProgrammingBacktracking

Data Structures:

String

Companies:

Adobe |Amazon |Apple |Avito |