Jobs

Interviews

Discussions

Generate Parentheses #5 Most Asked

Medium

Lucid Motors

1 view

Topics:

StringsRecursionDynamic Programming

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

Try coding it in LeetCode

Generate Parentheses #5 Most Asked

Medium

Lucid Motors

1 view

Topics:

StringsRecursionDynamic Programming

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

Try coding it in LeetCode

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 expected range for the input integer `n`? Specifically, can `n` be zero, and is there an upper bound I should consider?
The problem asks for 'all combinations'. Is there any specific order required for the output list of strings, for example, lexicographical order?
Just to be certain about the definition of 'well-formed', does it mean that at any point while scanning the string from left to right, the count of closing parentheses never exceeds the count of opening parentheses, and the total counts are equal at the end?
What should be the return value if the input `n` is 0? Should I return an empty list or a list containing an empty string?
Are there any constraints on the data type for `n`? For instance, should I anticipate non-integer or negative inputs, and how should they be handled?

Brute Force Solution

Approach

The problem asks us to find all the correctly formed combinations of parentheses for a given number of pairs. The brute force method is like trying every single possible arrangement of open and close parentheses and then checking each one to see if it's a valid combination.

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

First, figure out the total length of any valid combination. For a certain number of pairs, say 'n', the total length will always be twice that number.
Now, think about generating every single sequence of that length using only open and close parentheses. We'll build them one character at a time.
Start with an empty sequence. To grow it, we can either add an open parenthesis or a close parenthesis.
Repeat this process, adding one parenthesis at a time, exploring every possible choice at each step, until we have a sequence of the required total length.
This creates a huge list of every imaginable sequence of open and close parentheses of the correct length.
Finally, go through this entire list of generated sequences. For each one, carefully check if it follows the rules of valid parentheses (like never having more closing than opening parentheses at any point, and having an equal number of both in total).
Keep only the sequences that pass the check. This final collection is our answer.

Code Implementation

class Solution:
    def generateParenthesis(self, number_of_pairs: int) -> list[str]:
        all_possible_sequences = []
        total_length = 2 * number_of_pairs

        def generate_all_sequences(current_sequence):
            # Once the sequence reaches the target length, we stop this path and store the result.
            if len(current_sequence) == total_length:
                all_possible_sequences.append("".join(current_sequence))
                return

            # Explore adding an open parenthesis to the current sequence.
            current_sequence.append('(')
            generate_all_sequences(current_sequence)
            current_sequence.pop()

            # Explore adding a close parenthesis to the current sequence.
            current_sequence.append(')')
            generate_all_sequences(current_sequence)
            current_sequence.pop()

        def is_combination_valid(sequence_to_check: str) -> bool:
            balance_counter = 0
            for character in sequence_to_check:
                if character == '(':
                    balance_counter += 1
                else:
                    balance_counter -= 1
                
                # A negative balance means a closing parenthesis appeared without a matching open one.
                if balance_counter < 0:
                    return False
            
            # A valid combination must end with a zero balance, meaning equal open and close counts.
            return balance_counter == 0

        generate_all_sequences([])
        
        valid_combinations = []
        for sequence in all_possible_sequences:
            if is_combination_valid(sequence):
                valid_combinations.append(sequence)
        
        return valid_combinations

Big(O) Analysis

Time Complexity

O(2^(2n) * n) – The described brute-force approach first generates all possible sequences of parentheses of length 2n. Since there are two choices (open or close parenthesis) for each of the 2n positions, this results in 2^(2n) total sequences. For each of these generated sequences, we must then perform a validation check to see if it is a well-formed combination. This validation process involves iterating through the string of length 2n, which takes O(n) time. Therefore, the total time complexity is the number of sequences multiplied by the cost of validating each one, leading to O(2^(2n) * n).

Space Complexity

O(N * 2^(2N)) – The primary space consumption comes from storing all generated sequences before validation. Since there are 2^(2N) possible sequences of length 2N, and each sequence has a length of 2N, this list requires O(N * 2^(2N)) space. The recursion used to generate these sequences also contributes to the space complexity, adding a maximum of O(N) to the call stack for a sequence of length 2N. However, the storage for all generated sequences is the dominant factor in this brute-force approach.

Optimal Solution

Approach

To generate all valid combinations of parentheses, we can think of it as building them one character at a time. The key is to follow two simple rules at each step to ensure we only build valid sequences, avoiding the need to check them for correctness at the end.

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

Start building a combination from an empty string, keeping track of how many opening and closing parentheses we still need to add.
At any point, we have two choices: add an opening parenthesis or add a closing parenthesis.
Rule 1: We can always add an opening parenthesis as long as we haven't used all of them up.
Rule 2: We can only add a closing parenthesis if it wouldn't outnumber the opening ones we've already placed. This prevents invalid combinations like '())'.
We explore every possible path by recursively applying these two rules, adding one character at a time.
Whenever a combination reaches the correct total length (twice the number of pairs), we know it's a complete and valid solution, so we add it to our list of answers.
By following these rules, we systematically construct every possible valid combination without ever building an invalid one.

Code Implementation

class Solution:
    def generateParenthesis(self, number_of_pairs: int) -> list[str]:
        valid_combinations = []
        
        def build_combinations(current_string, open_parentheses_needed, close_parentheses_needed):
            # A combination is complete and valid when it reaches the target length.
            if len(current_string) == 2 * number_of_pairs:
                valid_combinations.append(current_string)
                return

            # Rule 1: We can add an opening parenthesis if we still have some left to place.
            if open_parentheses_needed > 0:
                build_combinations(current_string + '(', open_parentheses_needed - 1, close_parentheses_needed)

            # Rule 2: We can add a closing parenthesis only if it doesn't exceed the open ones.
            if close_parentheses_needed > open_parentheses_needed:
                build_combinations(current_string + ')', open_parentheses_needed, close_parentheses_needed - 1)

        # Start the recursive process with an empty string and the total counts for n pairs.
        build_combinations("", number_of_pairs, number_of_pairs)
        return valid_combinations

Big(O) Analysis

Time Complexity

O( (4^n) / (n * sqrt(n)) ) – The time complexity is determined by the number of valid parenthesis combinations, known as the n-th Catalan number, and the length of each combination. The recursive function explores a tree of possibilities; at each step in building a string of length 2n, we make choices, leading to a number of valid sequences proportional to the n-th Catalan number. Since each valid combination has a length of 2n, the total work is the number of combinations multiplied by the work to build each one. The Catalan number C(n) is asymptotically (4^n) / (n * sqrt(n)), and we perform O(n) work to construct each string, resulting in a total complexity of O(n * C(n)), which simplifies to O( (4^n) / sqrt(n) ) but is more precisely expressed as O( (4^n) / (n * sqrt(n)) ).

Space Complexity

O(N) – The space complexity is determined by the recursion depth and the storage for the current combination being built. The plain English explanation describes building a combination one character at a time, which requires a temporary data structure, like a string or character array, of length 2*N to hold the parentheses. The recursive nature of the solution, where we explore different paths by adding one character at a time, creates a call stack that can go as deep as 2*N, which is the total length of a valid combination. Therefore, the dominant factor is the recursion stack depth, which grows linearly with the input N, resulting in O(N) auxiliary space.

Edge Cases

Case	How to Handle
Input n = 0	The solution should return a list containing a single empty string, representing zero pairs of parentheses.
Input n = 1	The base case for recursion should correctly produce a list with the single valid combination "()".
Negative input for n (e.g., n = -1)	The function should return an empty list as no well-formed parentheses can be generated for a negative number of pairs.
Large input for n (e.g., n = 10 or more)	The number of solutions grows exponentially (Catalan numbers), so the solution must be efficient to avoid timeouts and manage memory.
Recursive solution stack depth	The maximum recursion depth will be 2*n, which is well within typical stack limits for reasonable constraints on n.
Intermediate string states that are not well-formed	The backtracking algorithm's constraints must ensure that the number of closing parentheses never exceeds the number of opening parentheses at any point.
Non-integer input for n (e.g., float, string)	Depending on the language, this might raise a type error or require explicit type checking to handle gracefully.
Final validation of parentheses count	The algorithm must ensure that each valid final string contains exactly n opening and n closing parentheses.

Input n = 0

How to Handle:

The solution should return a list containing a single empty string, representing zero pairs of parentheses.

Input n = 1

How to Handle:

The base case for recursion should correctly produce a list with the single valid combination "()".

Negative input for n (e.g., n = -1)

How to Handle:

The function should return an empty list as no well-formed parentheses can be generated for a negative number of pairs.

Large input for n (e.g., n = 10 or more)

How to Handle:

The number of solutions grows exponentially (Catalan numbers), so the solution must be efficient to avoid timeouts and manage memory.

Recursive solution stack depth

How to Handle:

The maximum recursion depth will be 2*n, which is well within typical stack limits for reasonable constraints on n.

Intermediate string states that are not well-formed

How to Handle:

The backtracking algorithm's constraints must ensure that the number of closing parentheses never exceeds the number of opening parentheses at any point.

Non-integer input for n (e.g., float, string)

How to Handle:

Depending on the language, this might raise a type error or require explicit type checking to handle gracefully.

Final validation of parentheses count

How to Handle:

The algorithm must ensure that each valid final string contains exactly n opening and n closing parentheses.

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 expected range for the input integer `n`? Specifically, can `n` be zero, and is there an upper bound I should consider?
The problem asks for 'all combinations'. Is there any specific order required for the output list of strings, for example, lexicographical order?
Just to be certain about the definition of 'well-formed', does it mean that at any point while scanning the string from left to right, the count of closing parentheses never exceeds the count of opening parentheses, and the total counts are equal at the end?
What should be the return value if the input `n` is 0? Should I return an empty list or a list containing an empty string?
Are there any constraints on the data type for `n`? For instance, should I anticipate non-integer or negative inputs, and how should they be handled?

Brute Force Solution

Approach

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

First, figure out the total length of any valid combination. For a certain number of pairs, say 'n', the total length will always be twice that number.
Now, think about generating every single sequence of that length using only open and close parentheses. We'll build them one character at a time.
Start with an empty sequence. To grow it, we can either add an open parenthesis or a close parenthesis.
Repeat this process, adding one parenthesis at a time, exploring every possible choice at each step, until we have a sequence of the required total length.
This creates a huge list of every imaginable sequence of open and close parentheses of the correct length.
Finally, go through this entire list of generated sequences. For each one, carefully check if it follows the rules of valid parentheses (like never having more closing than opening parentheses at any point, and having an equal number of both in total).
Keep only the sequences that pass the check. This final collection is our answer.

Code Implementation

class Solution:
    def generateParenthesis(self, number_of_pairs: int) -> list[str]:
        all_possible_sequences = []
        total_length = 2 * number_of_pairs

        def generate_all_sequences(current_sequence):
            # Once the sequence reaches the target length, we stop this path and store the result.
            if len(current_sequence) == total_length:
                all_possible_sequences.append("".join(current_sequence))
                return

            # Explore adding an open parenthesis to the current sequence.
            current_sequence.append('(')
            generate_all_sequences(current_sequence)
            current_sequence.pop()

            # Explore adding a close parenthesis to the current sequence.
            current_sequence.append(')')
            generate_all_sequences(current_sequence)
            current_sequence.pop()

        def is_combination_valid(sequence_to_check: str) -> bool:
            balance_counter = 0
            for character in sequence_to_check:
                if character == '(':
                    balance_counter += 1
                else:
                    balance_counter -= 1
                
                # A negative balance means a closing parenthesis appeared without a matching open one.
                if balance_counter < 0:
                    return False
            
            # A valid combination must end with a zero balance, meaning equal open and close counts.
            return balance_counter == 0

        generate_all_sequences([])
        
        valid_combinations = []
        for sequence in all_possible_sequences:
            if is_combination_valid(sequence):
                valid_combinations.append(sequence)
        
        return valid_combinations

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

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

Start building a combination from an empty string, keeping track of how many opening and closing parentheses we still need to add.
At any point, we have two choices: add an opening parenthesis or add a closing parenthesis.
Rule 1: We can always add an opening parenthesis as long as we haven't used all of them up.
Rule 2: We can only add a closing parenthesis if it wouldn't outnumber the opening ones we've already placed. This prevents invalid combinations like '())'.
We explore every possible path by recursively applying these two rules, adding one character at a time.
Whenever a combination reaches the correct total length (twice the number of pairs), we know it's a complete and valid solution, so we add it to our list of answers.
By following these rules, we systematically construct every possible valid combination without ever building an invalid one.

Code Implementation

class Solution:
    def generateParenthesis(self, number_of_pairs: int) -> list[str]:
        valid_combinations = []
        
        def build_combinations(current_string, open_parentheses_needed, close_parentheses_needed):
            # A combination is complete and valid when it reaches the target length.
            if len(current_string) == 2 * number_of_pairs:
                valid_combinations.append(current_string)
                return

            # Rule 1: We can add an opening parenthesis if we still have some left to place.
            if open_parentheses_needed > 0:
                build_combinations(current_string + '(', open_parentheses_needed - 1, close_parentheses_needed)

            # Rule 2: We can add a closing parenthesis only if it doesn't exceed the open ones.
            if close_parentheses_needed > open_parentheses_needed:
                build_combinations(current_string + ')', open_parentheses_needed, close_parentheses_needed - 1)

        # Start the recursive process with an empty string and the total counts for n pairs.
        build_combinations("", number_of_pairs, number_of_pairs)
        return valid_combinations

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Input n = 0	The solution should return a list containing a single empty string, representing zero pairs of parentheses.
Input n = 1	The base case for recursion should correctly produce a list with the single valid combination "()".
Negative input for n (e.g., n = -1)	The function should return an empty list as no well-formed parentheses can be generated for a negative number of pairs.
Large input for n (e.g., n = 10 or more)	The number of solutions grows exponentially (Catalan numbers), so the solution must be efficient to avoid timeouts and manage memory.
Recursive solution stack depth	The maximum recursion depth will be 2*n, which is well within typical stack limits for reasonable constraints on n.
Intermediate string states that are not well-formed	The backtracking algorithm's constraints must ensure that the number of closing parentheses never exceeds the number of opening parentheses at any point.
Non-integer input for n (e.g., float, string)	Depending on the language, this might raise a type error or require explicit type checking to handle gracefully.
Final validation of parentheses count	The algorithm must ensure that each valid final string contains exactly n opening and n closing parentheses.

Input n = 0

How to Handle:

The solution should return a list containing a single empty string, representing zero pairs of parentheses.

Input n = 1

How to Handle:

The base case for recursion should correctly produce a list with the single valid combination "()".

Negative input for n (e.g., n = -1)

How to Handle:

The function should return an empty list as no well-formed parentheses can be generated for a negative number of pairs.

Large input for n (e.g., n = 10 or more)

How to Handle:

The number of solutions grows exponentially (Catalan numbers), so the solution must be efficient to avoid timeouts and manage memory.

Recursive solution stack depth

How to Handle:

The maximum recursion depth will be 2*n, which is well within typical stack limits for reasonable constraints on n.

Intermediate string states that are not well-formed

How to Handle:

The backtracking algorithm's constraints must ensure that the number of closing parentheses never exceeds the number of opening parentheses at any point.

Non-integer input for n (e.g., float, string)

How to Handle:

Depending on the language, this might raise a type error or require explicit type checking to handle gracefully.

Final validation of parentheses count

How to Handle:

The algorithm must ensure that each valid final string contains exactly n opening and n closing parentheses.

0/0 Lucid Motors questions completed

0/0 completed