Generate Parentheses - Python Solution

1. Introduction

The "Generate Parentheses" problem is an intriguing and common challenge in computer science, often appearing in coding interviews. The task is to generate all possible combinations of well-formed parentheses given several pairs. This problem is a good example of using backtracking techniques to explore all possible solutions.

Problem

Given an integer n representing the number of pairs of parentheses, write a function to generate all possible combinations of well-formed parentheses.

2. Solution Steps

1. Understand that well-formed parentheses require an equal number of opening and closing brackets in the correct order.

2. Use a recursive function to generate all possible combinations.

3. Keep track of the number of opening and closing brackets.

4. Only add an opening bracket if we have less than n opening brackets.

5. Only add a closing bracket if we have more opening brackets than closing brackets.

6. When the current string reaches the length of 2 * n, add it to the result list.

3. Code Program

# Function to generate parentheses
def generateParenthesis(n):
    def backtrack(S, left, right):
        # If the string is of the correct length, add it to the results
        if len(S) == 2 * n:
            res.append(S)
            return
        # Add an opening bracket if we have less than `n` opening brackets
        if left < n:
            backtrack(S + '(', left + 1, right)
        # Add a closing bracket if we have more opening than closing brackets
        if right < left:
            backtrack(S + ')', left, right + 1)

    res = []
    backtrack('', 0, 0)
    return res

# Testing the function
print(generateParenthesis(3))

Output:

['((()))', '(()())', '(())()', '()(())', '()()()']

Explanation:

1. Initialization: The function generateParenthesis initializes a backtrack function which is used to generate the combinations.

2. Backtracking: The backtrack function is recursive and builds the string S. It takes parameters left and right to keep track of the number of opening and closing brackets.

3. Adding Brackets: It adds an opening bracket if the number of left brackets is less than n, and a closing bracket if the number of right brackets is less than the number of left brackets.

4. Checking Length: When the length of S is 2 * n, it means a valid combination is formed, and it's added to the result list.

5. Result: The function returns all the possible well-formed combinations of parentheses.