Solution For Generate Parentheses

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.

Step by Step Implementation For Generate Parentheses

public class Solution {
    public List generateParenthesis(int n) {
        List res = new ArrayList<>();
        // Call the recursive helper function to generate all the possible strings
        generateAll(new char[2 * n], 0, res);
        return res;
    }
    
    // Generate all possible strings that consist of n pairs of parentheses
    public void generateAll(char[] current, int pos, List result) {
        // If we have reached the end of the array, then the string is valid
        if (pos == current.length) {
            // Convert the char array to a string and add it to the result
            result.add(new String(current));
        } else {
            // The current character can be either '(' or ')'
            // Try both and recurse
            current[pos] = '(';
            generateAll(current, pos+1, result);
            current[pos] = ')';
            generateAll(current, pos+1, result);
        }
    }
}

def generateParenthesis(self, n: int) -> List[str]:
    # Base case
    if n == 0:
        return []
    
    # Recursive case
    else:
        # Generate all possible strings of length n-1
        strings = self.generateParenthesis(n-1)
        
        # Add a '(' to the beginning of each string and ')' to the end of each string
        for i in range(len(strings)):
            strings[i] = '(' + strings[i] + ')'
        
        return strings

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

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

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

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

public IList GenerateParenthesis(int n) 
{
    IList result = new List();
    GenerateParenthesisHelper(result, new char[2 * n], 0, n, 0, 0);
    return result;
}

private void GenerateParenthesisHelper(IList result, char[] current, int index, int n, int open, int close)
{
    if (index == 2 * n)
    {
        result.Add(new string(current));
        return;
    }

    if (open < n)
    {
        current[index] = '(';
        GenerateParenthesisHelper(result, current, index + 1, n, open + 1, close);
    }

    if (close < open)
    {
        current[index] = ')';
        GenerateParenthesisHelper(result, current, index + 1, n, open, close + 1);
    }
}