## Description

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

## Example 1:

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

## Example 2:

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

## Solution:

- This solution will use backtracking
- Backtracking is a systematic way of iterating through all possible combinations
- These types of problems follow a similar pattern

```
// function to return answer and adds the params to the
// recursive backtracking function
function setup(n) {
// answer to return
// recursive backtrack(answer, emptyCombination);
// return answer;
};
function backtrack(ans, curentCombination) {
// if (base case) {
// add curentCombination to answer
//}
// logic for recursive call to add items
// to curentCombination
}
```

- We will recursively construct valid combinations of parens and return them in an array
- Recursive algorithms require a base case in order to break out of the recursive calls
- Let's think about a possible base case
- In this problem, all opening parens must have a corresponding closing parens (opening count ==== closing count). Therefore the total number of parens in a valid combination = opening params + closing params = n x 2
- Since any valid combination cannot be more than n x 2 in length, let's use this check as our base case
- Once we hit the base case, we know that the current combination is valid and can be added to our output array

```
if (cur.length == max * 2) {
ans.push(cur);
return;
}
```

- When adding to our combination we can either add an opening or closing paren and we must have n amount of each
- For the combination to be valid we must add an opening paren first
- Once we've added this paren in the current combination we will add more until we reach our max limit (n)
- We can repeat this logic through recursive calls

```
if (open < max)
backtrack(ans, cur+"(", open+1, close, max)
```

- Once we have added the opening parens we must add the closing parens through similar recursive logic

```
if (close < open)
backtrack(ans, cur+")", open, close+1, max);
```

- We keep track of each type of paren in our current combination starting at 0 for each in our setup function
- Our current combination will start as an empty string and will have parens added to it on each call
- The setup function will look like this

```
var generateParenthesis = function(n) {
const ans = [];
backtrack(ans, "", 0, 0, n);
return ans;
};
```

### Full solution

```
var generateParenthesis = function(n) {
const ans = [];
backtrack(ans, "", 0, 0, n);
return ans;
};
function backtrack(ans, cur, open, close, max) {
if (cur.length == max * 2) {
ans.push(cur);
return;
}
if (open < max)
backtrack(ans, cur+"(", open+1, close, max);
if (close < open)
backtrack(ans, cur+")", open, close+1, max);
}
```

## Discussion (0)