New update is available. Click here to update.

Last Updated: 2 Dec, 2020

Moderate

```
For βNβ = 3,
All possible combinations are:
((()))
(()())
(())()
()(())
()()()
```

```
Input consists of a single line containing a single integer βNβ, representing the number of pairs in the parentheses.
```

```
Print list of strings denoting all possible combinations for the given integer in a lexicographically ascending order.
```

```
You are not required to print anything, it has already been taken care of. Just implement the function.
```

Approaches

We will try to fix both the opening and closing brackets at each index if it can lead to a valid parenthesis. For a parenthesis to be valid, at each index the number of the opening bracket in the prefix of that index should be greater than or equal to the number of closing brackets.

Algorithm:

generate function:

- It will take a number of arguments:
- βTOTALβ - an integer representing the total number of characters i.e twice the number of pairs.
- βOPENβ - an integer representing the number of opening brackets till now.
- βCLOSEβ - an integer representing the number of closing brackets till now.
- βSβ - a string representing the parenthesis till now.
- βANSβ - a vector of string to store all the generated parenthesis.

- If the size of the string becomes equal to βTOTALββ, that means that a valid parenthesis is generated, we will store it in the βANSβ vector.
- If βOPENβ is greater than βCLOSEβ,
- then we can give a closing bracket at this index.
- Again if βOPENβ is less than βTOTALβ / 2, we can also give an opening bracket at this index.

- Else we can only give an opening bracket at this index.

given function:

- Declare a variable βTOTALβ with a value twice as βNβ, since each pair consists of two characters.
- Declare a vector of strings βANSβ to store all the valid parentheses.
- Call the generate function with zero opening bracket, zero closing bracket, and an empty string.
- Finally, return the βANSβ vector.