Generate Parentheses - Leetcode Solution

Problem Statement:

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

Example:

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

Solution:

The problem can be solved using backtracking technique. Backtracking is an algorithmic paradigm that follows a trial and error approach to solve problems. It is one of the most basic algorithmic techniques for solving problems recursively. In backtracking, we start with some initial solution and then we incrementally build on this solution, always checking if the current solution satisfies the problem constraints, until we get the desired solution.

Here's the algorithm to solve the given problem:

1. Initialize an empty list to store the valid parentheses combinations.

2. Define a recursive function that takes four parameters: the current string, the number of opening brackets, the number of closing brackets, and the maximum number of brackets.

3. If the length of the current string is equal to 2 times the maximum number of brackets, append it to the list of valid combinations.

4. If the number of opening brackets is less than the maximum number, call the recursive function again with an additional opening bracket.

5. If the number of closing brackets is less than the number of opening brackets, call the recursive function again with an additional closing bracket.

6. Implement the recursive function in a depth-first search manner and backtrack when necessary.

Let's see the Python code implementation of the above algorithm:

def generateParenthesis(n: int) -> List[str]:

def backtrack(s, open, close, max):

    if len(s) == max * 2:
        res.append(s)
        return

    if open < max:
        backtrack(s+'(', open+1, close, max)

    if close < open:
        backtrack(s+')', open, close+1, max)

res = []
backtrack("", 0, 0, n)
return res

In the above code, we have defined a function called generateParenthesis, which takes an integer n as input and returns a list of strings. Inside the function, we have defined another recursive function called backtrack.

The backtrack function takes four parameters, string s, integers open, close, and max. Here, s represents the current string with parentheses, open represents the number of opening brackets, close represents the number of closing brackets, and max represents the maximum number of brackets.

If the length of s is equal to 2 times max, it means we have generated a valid combinations of n pairs of parentheses.

In the next two if statements, we call the backtrack function recursively to generate the valid combinations. If open is less than max, it means we can add an opening bracket, and if close is less than open, it means we can add a closing bracket.

Finally, we initialize an empty list, call the backtrack function with an empty string, and return the list of valid combinations.

Time Complexity:

The time complexity of the above algorithm is O(4^n/n^(1/2)), where n is the number of pairs of parentheses. This is because we generate all possible combinations of 2n parentheses, and for each combination, we check if it is a valid combination. The number of valid combinations is Catalan number, which is proportional to 4^n/n^(1/2).

Space Complexity:

The space complexity of the above algorithm is O(n), where n is the number of pairs of parentheses. This is because we use a recursive function to generate the valid combinations, and the recursion depth is limited by n.

1