Algorithm
Problem Name: 22. Generate Parentheses
Problem Link: https://leetcode.com/problems/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;
}
Input
n = 3
Output
["((()))","(()())","(())()","()(())","()()()"]
#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();
}
}
};
Input
n = 1
Output
["()"]
#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) {
result.add(new StringBuilder(sb.toString()).toString());
}
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);
}
}
}
Input
n = 1
Output
["()"]
#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);
}
Input
n = 3
Output
["((()))","(()())","(())()","()(())","()()()"]
#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]
Input
n = 3
Output
["((()))","(()())","(())()","()(())","()()()"]
#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);
results.Add(s);
return;
}
GenerateParenthesis(l - 1, r, results, s + "(");
if (r > l)
{
GenerateParenthesis(l, r - 1, results, s + ")");
}
}
}
}
Input
n = 1
Output
["()"]