## Algorithm

Problem Name: 22. Generate Parentheses

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: ["()"]
```

Constraints:

• `1 <= n <= 8`

## Code Examples

### #1 Code Example with C Programming

```Code - C Programming```

``````
void bt(char ***p, int *sz, int *k, int n, char *buff, int l, int open, int close) {
if (open == n && close == n) {
if (*sz == *k) {
(*sz) *= 2;
*p = realloc(*p, (*sz) * sizeof(char *));
//assert(*p);
}
(*p)[(*k) ++] = strdup(buff);
return;
}
if (open  <  n) {
buff[l] = '(';
bt(p, sz, k, n, buff, l + 1, open + 1, close);
}
if (close  <  open) {
buff[l] = ')';
bt(p, sz, k, n, buff, l + 1, open, close + 1);
}
}
char** generateParenthesis(int n, int* returnSize) {
#if 0
char **p, *buff;
int i, k, sz;

sz = 100;
p = malloc(sz * sizeof(char *));
//assert(p);

buff = malloc(n * 2 + 1);
//assert(buff);
buff[n * 2] = 0;

k = 0;
bt(&p, &sz, &k, n, buff, 0, 0, 0);

*returnSize = k;

free(buff);
#else  // Because of memory allocation/freeing, this is much slower than above!!!
int *sz, *nn;
char ***pp, **p, **p1, **p2, *buff;
int i, j, a, b, x, y, l, k, h;

buff = calloc(n * 2 + 1, sizeof(char));
//assert(buff);

sz = calloc(n + 1, sizeof(int));
nn = calloc(n + 1, sizeof(int));
pp = malloc((n + 1) * sizeof(char **));
//assert(sz && nn && pp);

sz[0] = 1;
pp[0] = calloc(sz[0], sizeof(char *));
pp[0][nn[0] ++] = strdup(buff);

for (i = 1; i  < = n; i ++) {     // f(n) = '('f(0)')'f(n-1), '('f(1)')'f(n-2), ...'('f(n-1)')'f(0)
for (j = 0; j  <  i; j ++) {
a = nn[j];
p1 = pp[j];

b = nn[i - j - 1];
p2 = pp[i - j - 1];

l = 0;
buff[l ++] = '(';
for (x = 0; x  <  a; x ++) {
k = l + sprintf(&buff[l], "%s", p1[x]);
buff[k ++] = ')';
for (y = 0; y  <  b; y ++) {
h = k + sprintf(&buff[k], "%s", p2[y]);
buff[h] = 0;
if (sz[i] == 0) {
sz[i] = 10;
pp[i] = malloc(sz[i] * sizeof(char *));
//assert(pp[i]);
} else if (nn[i] == sz[i]) {
sz[i] *= 2;
pp[i] = realloc(pp[i], sz[i] * sizeof(char *));
//assert(pp[i]);
}
pp[i][nn[i] ++] = strdup(buff);
}
}
}
}
k = nn[n];
*returnSize = k;
p = malloc(k * sizeof(char *));
memcpy(p, pp[n], k * sizeof(char *));

for (i = 0; i  < = n; i ++) {
free(pp[i]);
}
free(sz); free(nn); free(pp);
#endif

return p;
}
``````
Copy The Code &

Input

cmd
n = 3

Output

cmd
["((()))","(()())","(())()","()(())","()()()"]

### #2 Code Example with C++ Programming

```Code - C++ Programming```

``````
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string>res;
string path = "";
DFS(res, n, 0, 0, path);
return res;
}

void DFS(vector < string>& res, int n, int k, int left, string& path){
if(left > n) return;
if(k == n){
if(left == 0) res.push_back(path);
return;
}
path.push_back('(');
DFS(res, n, k, left + 1, path);
path.pop_back();

if(left != 0){
path.push_back(')');
DFS(res, n, k + 1, left - 1, path);
path.pop_back();
}
}
};
``````
Copy The Code &

Input

cmd
n = 1

Output

cmd
["()"]

### #3 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {
public List generateParenthesis(int n) {
List result = new ArrayList<>();
helper(result, 0, 0, n, new StringBuilder());
return result;
}

private void helper(List < String> result, int start, int end, int n, StringBuilder sb) {
if (start + end == 2 * n) {
if (start == end) {
}
return;
}
if (start > end) {
sb.append('(');
helper(result, start + 1, end, n, sb);
sb.deleteCharAt(sb.length() - 1);
sb.append(')');
helper(result, start, end + 1, n, sb);
sb.deleteCharAt(sb.length() - 1);
} else if (start == end) {
sb.append('(');
helper(result, start + 1, end, n, sb);
sb.deleteCharAt(sb.length() - 1);
}
}
}

``````
Copy The Code &

Input

cmd
n = 1

Output

cmd
["()"]

### #4 Code Example with Javascript Programming

```Code - Javascript Programming```

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

``````
Copy The Code &

Input

cmd
n = 3

Output

cmd
["((()))","(()())","(())()","()(())","()()()"]

### #5 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
bfs = [(0, 0, '')]
for c in range(n * 2):
bfs = [(l + 1, r, s + '(') for l, r, s in bfs if l + 1 <= n] + [(l, r + 1, s + ')') for l, r, s in bfs if l - r]
return [s for l, r, s in bfs]
``````
Copy The Code &

Input

cmd
n = 3

Output

cmd
["((()))","(()())","(())()","()(())","()()()"]

### #6 Code Example with C# Programming

```Code - C# Programming```

``````
using System.Collections.Generic;

namespace LeetCode
{
public class _022_GenerateParentheses
{
public IList < string> GenerateParenthesis(int n)
{
var results = new List();
if (n > 0) { GenerateParenthesis(n, n, results, ""); }
return results;
}

void GenerateParenthesis(int l, int r, IList < string> results, string s)
{
if (l == 0)
{
s += new string(')', r);
return;
}

GenerateParenthesis(l - 1, r, results, s + "(");
if (r > l)
{
GenerateParenthesis(l, r - 1, results, s + ")");
}
}
}
}
``````
Copy The Code &

Input

cmd
n = 1

Output

cmd
["()"]