> For the complete documentation index, see [llms.txt](https://joshualbarb.gitbook.io/leetcode-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://joshualbarb.gitbook.io/leetcode-problems/backtracking/generate-parantheses.md).

# Generate Parantheses

## Problem

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

{% hint style="info" %}
For example:

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

```
Input: n = 1
Output: ["()"]
```

{% endhint %}

### Thought Process

![](/files/-MNKVjnhzhWsBvfglC5p)

![](/files/-MNKYFRyQbC9O6MgPCIy)

* We aren't given a "normal" input to recurse on like we usually get with backtracking problems but we are actually recursing on bracket placements. 

* We will add the closing bracket if there is at least one open bracket placed down. For n open brackets there must be n closing brackets to complement, and the final valid placement will be of length n\*2.

* ( (( ((( ((() ((()) ((())) i (() (()( (()() (()()) (()) (())( (())() () ()( ()(( ()(() ()(()) ()() ()()( ()()()

## Solution

```
class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        soln = []
        self.helper(soln, "", n,n,n)
        return soln
    
    def helper(self, soln, s, left, right, n):
        if len(s) == (n*2):
            soln.append(s)
        if left > 0:
            self.helper(soln, s+"(", left-1,right,n)
        if right > left:
            self.helper(soln, s+")", left, right-1, n)
        
```

## Key Points

* In this problem, you have to choose between left and right parenthesis. 

* The idea here is to only add '(' and ')' that we know will guarantee us a solution (instead of adding 1 too many close). Once we add a '(' we will then discard it and try a ')' which can only close a valid '('. Each of these steps are recursively called.

* Every time you choose a "(" means making another ")" available.

## Time Complexity

**Time:** $$O(2^{2n})$$because we need to make a choice of either left or right (that makes it $$2^n$$ ) and then we need *n* left parthesis and *n* right parenthesis ($$2n$$).

**Space:** $$O(n)$$ as this will be the max depth of the recursion stack (look at Thought Process picture)