# 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.