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


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://joshualbarb.gitbook.io/leetcode-problems/backtracking/generate-parantheses.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.