Jobs

Interviews

Discussions

Generate Parentheses

Medium

Grammarly

0 views

Topics:

StringsRecursionBacktracking

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

Generate Parentheses

Medium

Grammarly

0 views

Topics:

StringsRecursionBacktracking

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

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the valid range for the input integer n?
Should the order of the strings in the output list matter?
Can n be zero, and if so, what should the output be?
Do we need to ensure the parentheses are strictly balanced, or are there any exceptions to that rule?
Are there any memory constraints I should consider, given the potentially exponential growth of the solution space?

Brute Force Solution

Approach

The goal is to generate all possible valid combinations of parentheses given a number 'n', where 'n' represents the number of pairs of parentheses. The brute force method involves creating every possible sequence of parentheses and then checking if each sequence is valid.

Here's how the algorithm would work step-by-step:

First, create every possible string of parentheses of length 2*n. This means trying out every combination of open and close parentheses in every possible position.
Now, take each generated string and check if it's a valid combination of parentheses.
To check if a string is valid, make sure that for every closing parenthesis, there's a corresponding open parenthesis before it. Also, at the end, the total number of open parentheses must equal the total number of closing parentheses.
If a string passes this validity check, then it's a valid combination. If not, discard it.
Collect all the strings that are valid combinations of parentheses.

Code Implementation

def generate_parentheses_brute_force(number_pairs):
    all_combinations = []

    def generate_all_sequences(current_string, string_length):
        if len(current_string) == string_length:
            all_combinations.append(current_string)
            return

        generate_all_sequences(current_string + '(', string_length)
        generate_all_sequences(current_string + ')', string_length)

    generate_all_sequences('', 2 * number_pairs)

    valid_combinations = []
    for combination in all_combinations:
        if is_valid(combination):
            valid_combinations.append(combination)

    return valid_combinations

def is_valid(parentheses_string):
    balance = 0
    # Ensure that there isn't a closing parenthesis without a matching open parenthesis
    for character in parentheses_string:
        if character == '(': 
            balance += 1
        else:
            balance -= 1
        if balance < 0:
            return False

    # Check to ensure an equal number of open/close parentheses.
    if balance == 0:
        return True
    else:
        return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(2^(2n) * n) – Generating all possible strings of length 2n, where each position can be either '(' or ')', takes O(2^(2n)) time because there are 2^(2n) possible combinations. For each of these strings, we need to check its validity. Checking validity requires iterating through the string of length 2n, which takes O(n) time. Therefore, the overall time complexity is the product of these two, resulting in O(2^(2n) * n).

Space Complexity

O(n*2^2n) – The algorithm generates all possible parenthesis strings of length 2*n. In the worst case, it stores up to 2^(2n) strings, each of length 2n, in memory to check their validity. Then, it collects valid combinations of parentheses and returns them as a list. This list can contain at most 2^(2n) elements of maximum length 2n. Therefore, the space complexity is O(n*2^2n) since the list stores strings of length 2n.

Optimal Solution

Approach

The most efficient way to generate valid parentheses combinations is to build them step-by-step, always maintaining a valid structure. We achieve this by tracking available open and closed parentheses, only adding them if they lead to a balanced state.

Here's how the algorithm would work step-by-step:

Imagine you're building parenthesis strings piece by piece.
You always start with an open parenthesis, because that's how balanced sets begin.
Keep track of how many open and closing parentheses you've used so far, and how many are still available.
You can add an open parenthesis as long as you haven't used up all the available open parentheses.
You can add a closing parenthesis only if there are more open parentheses already in the string than closing parentheses, ensuring you're always closing something that's open.
Keep adding open or closing parentheses following the above rules until you've used all available open and closing parentheses. At that point, you have a valid combination.
Repeat the process, trying different combinations of open and closing parentheses until you've generated all possible valid combinations.

Code Implementation

def generate_parenthesis(number):
    results = []

    def backtrack(current_string, open_count, close_count):
        # Base case: if we've used all parentheses, add to results.
        if open_count == number and close_count == number:
            results.append(current_string)
            return

        # Add an open parenthesis if we have available open parentheses.
        if open_count < number:
            backtrack(current_string + '(', open_count + 1, close_count)

        # Only add a closing parenthesis if it's valid.
        if close_count < open_count:
            backtrack(current_string + ')', open_count, close_count + 1)

    # Initiate backtracking from an empty string
    backtrack("", 0, 0)

    return results

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

O(4^n / sqrt(n)) – The number of valid parentheses strings of length 2n is given by the nth Catalan number, which is approximately 4^n / (n * sqrt(n)). The recursive function explores all possible combinations of open and close parentheses. Since each valid combination is of length 2n, and each function call takes O(1) time, the time complexity is proportional to the number of valid combinations. The number of valid combinations is bounded by the nth Catalan number, resulting in a time complexity of O(4^n / (n * sqrt(n))). After simplification (dropping the constant n under the exponent, and n in denominator) this approximation simplifies to O(4^n / sqrt(n)).

Space Complexity

O(N) – The algorithm uses recursion to explore different combinations of parentheses. The maximum depth of the recursion is 2N, where N is the number of pairs of parentheses, as each level represents a decision to add either an open or a close parenthesis. Each recursive call stores a string of length at most 2N. Additionally, we accumulate all valid combinations into a list. In the worst case, the number of valid combinations can grow exponentially, but the length of each valid string is 2N. Therefore, the space is dominated by the depth of the recursion stack and the string being built, resulting in O(N) auxiliary space due to the recursion stack.

Edge Cases

Case	How to Handle
n = 0	Return an empty string or a list containing an empty string, as no parentheses are needed.
n = 1	Return a list containing only '()' as the only valid combination.
Large n (e.g., n > 15)	The number of valid parentheses combinations grows exponentially, so the solution should be efficient in terms of memory and time complexity using backtracking or dynamic programming to avoid exceeding recursion depth limits and memory constraints.
Negative input for n	Throw an exception or return an empty list, as the number of pairs cannot be negative.
Non-integer input for n	Throw an exception, as the number of pairs must be an integer.
Maximum recursion depth exceeded for very large n	Consider iterative dynamic programming as an alternative to recursion to avoid stack overflow.
n is a floating point number	Cast n to integer type and proceed only if the value is positive; otherwise, handle it as invalid input.
Solution produces duplicate parenthesis combinations	Ensure that the algorithm only adds valid combinations (balanced) and the data structure storing solutions like set can guarantee uniqueness.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the valid range for the input integer n?
Should the order of the strings in the output list matter?
Can n be zero, and if so, what should the output be?
Do we need to ensure the parentheses are strictly balanced, or are there any exceptions to that rule?
Are there any memory constraints I should consider, given the potentially exponential growth of the solution space?

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

First, create every possible string of parentheses of length 2*n. This means trying out every combination of open and close parentheses in every possible position.
Now, take each generated string and check if it's a valid combination of parentheses.
To check if a string is valid, make sure that for every closing parenthesis, there's a corresponding open parenthesis before it. Also, at the end, the total number of open parentheses must equal the total number of closing parentheses.
If a string passes this validity check, then it's a valid combination. If not, discard it.
Collect all the strings that are valid combinations of parentheses.

Code Implementation

def generate_parentheses_brute_force(number_pairs):
    all_combinations = []

    def generate_all_sequences(current_string, string_length):
        if len(current_string) == string_length:
            all_combinations.append(current_string)
            return

        generate_all_sequences(current_string + '(', string_length)
        generate_all_sequences(current_string + ')', string_length)

    generate_all_sequences('', 2 * number_pairs)

    valid_combinations = []
    for combination in all_combinations:
        if is_valid(combination):
            valid_combinations.append(combination)

    return valid_combinations

def is_valid(parentheses_string):
    balance = 0
    # Ensure that there isn't a closing parenthesis without a matching open parenthesis
    for character in parentheses_string:
        if character == '(': 
            balance += 1
        else:
            balance -= 1
        if balance < 0:
            return False

    # Check to ensure an equal number of open/close parentheses.
    if balance == 0:
        return True
    else:
        return False

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Imagine you're building parenthesis strings piece by piece.
You always start with an open parenthesis, because that's how balanced sets begin.
Keep track of how many open and closing parentheses you've used so far, and how many are still available.
You can add an open parenthesis as long as you haven't used up all the available open parentheses.
You can add a closing parenthesis only if there are more open parentheses already in the string than closing parentheses, ensuring you're always closing something that's open.
Keep adding open or closing parentheses following the above rules until you've used all available open and closing parentheses. At that point, you have a valid combination.
Repeat the process, trying different combinations of open and closing parentheses until you've generated all possible valid combinations.

Code Implementation

def generate_parenthesis(number):
    results = []

    def backtrack(current_string, open_count, close_count):
        # Base case: if we've used all parentheses, add to results.
        if open_count == number and close_count == number:
            results.append(current_string)
            return

        # Add an open parenthesis if we have available open parentheses.
        if open_count < number:
            backtrack(current_string + '(', open_count + 1, close_count)

        # Only add a closing parenthesis if it's valid.
        if close_count < open_count:
            backtrack(current_string + ')', open_count, close_count + 1)

    # Initiate backtracking from an empty string
    backtrack("", 0, 0)

    return results

Try it yourself on LeetCode

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
n = 0	Return an empty string or a list containing an empty string, as no parentheses are needed.
n = 1	Return a list containing only '()' as the only valid combination.
Large n (e.g., n > 15)	The number of valid parentheses combinations grows exponentially, so the solution should be efficient in terms of memory and time complexity using backtracking or dynamic programming to avoid exceeding recursion depth limits and memory constraints.
Negative input for n	Throw an exception or return an empty list, as the number of pairs cannot be negative.
Non-integer input for n	Throw an exception, as the number of pairs must be an integer.
Maximum recursion depth exceeded for very large n	Consider iterative dynamic programming as an alternative to recursion to avoid stack overflow.
n is a floating point number	Cast n to integer type and proceed only if the value is positive; otherwise, handle it as invalid input.
Solution produces duplicate parenthesis combinations	Ensure that the algorithm only adds valid combinations (balanced) and the data structure storing solutions like set can guarantee uniqueness.