# 22. Generate Parentheses

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


Constraints:

• 1 <= n <= 8

## Solutions

Solution 1: DFS + Pruning

The range of $n$ in the problem is $[1, 8]$, so we can directly solve this problem through “brute force search + pruning”.

We design a function $dfs(l, r, t)$, where $l$ and $r$ represent the number of left and right brackets respectively, and $t$ represents the current bracket sequence. Then we can get the following recursive structure:

• If $l \gt n$ or $r \gt n$ or $l \lt r$, then the current bracket combination $t$ is invalid, return directly;
• If $l = n$ and $r = n$, then the current bracket combination $t$ is valid, add it to the answer array ans, and return directly;
• We can choose to add a left bracket, and recursively execute dfs(l + 1, r, t + "(");
• We can also choose to add a right bracket, and recursively execute dfs(l, r + 1, t + ")").

The time complexity is $O(2^{n\times 2} \times n)$, and the space complexity is $O(n)$.

• class Solution {
private List<String> ans = new ArrayList<>();
private int n;

public List<String> generateParenthesis(int n) {
this.n = n;
dfs(0, 0, "");
return ans;
}

private void dfs(int l, int r, String t) {
if (l > n || r > n || l < r) {
return;
}
if (l == n && r == n) {
return;
}
dfs(l + 1, r, t + "(");
dfs(l, r + 1, t + ")");
}
}

• class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> ans;
function<void(int, int, string)> dfs = [&](int l, int r, string t) {
if (l > n || r > n || l < r) return;
if (l == n && r == n) {
ans.push_back(t);
return;
}
dfs(l + 1, r, t + "(");
dfs(l, r + 1, t + ")");
};
dfs(0, 0, "");
return ans;
}
};

• class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def dfs(l, r, t):
if l > n or r > n or l < r:
return
if l == n and r == n:
ans.append(t)
return
dfs(l + 1, r, t + '(')
dfs(l, r + 1, t + ')')

ans = []
dfs(0, 0, '')
return ans

############

class Solution(object):
def generateParenthesis(self, n):
"""
:type n: int
:rtype: List[str]
"""

def dfs(left, path, res, n):
if len(path) == 2 * n:
if left == 0:
res.append("".join(path))
return

if left < n:
path.append("(")
dfs(left + 1, path, res, n)
path.pop()
if left > 0:
path.append(")")
dfs(left - 1, path, res, n)
path.pop()

res = []
dfs(0, [], res, n)
return res


• func generateParenthesis(n int) (ans []string) {
var dfs func(int, int, string)
dfs = func(l, r int, t string) {
if l > n || r > n || l < r {
return
}
if l == n && r == n {
ans = append(ans, t)
return
}
dfs(l+1, r, t+"(")
dfs(l, r+1, t+")")
}
dfs(0, 0, "")
return ans
}

• function generateParenthesis(n: number): string[] {
function dfs(l, r, t) {
if (l > n || r > n || l < r) {
return;
}
if (l == n && r == n) {
ans.push(t);
return;
}
dfs(l + 1, r, t + '(');
dfs(l, r + 1, t + ')');
}
let ans = [];
dfs(0, 0, '');
return ans;
}


• /**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function (n) {
function dfs(l, r, t) {
if (l > n || r > n || l < r) {
return;
}
if (l == n && r == n) {
ans.push(t);
return;
}
dfs(l + 1, r, t + '(');
dfs(l, r + 1, t + ')');
}
let ans = [];
dfs(0, 0, '');
return ans;
};


• impl Solution {
fn dfs(left: i32, right: i32, s: &mut String, res: &mut Vec<String>) {
if left == 0 && right == 0 {
res.push(s.clone());
return;
}
if left > 0 {
s.push('(');
Self::dfs(left - 1, right, s, res);
s.pop();
}
if right > left {
s.push(')');
Self::dfs(left, right - 1, s, res);
s.pop();
}
}

pub fn generate_parenthesis(n: i32) -> Vec<String> {
let mut res = Vec::new();
Self::dfs(n, n, &mut String::new(), &mut res);
res
}
}


• class Solution {
/**
* @param int $n * @return string[] */ function generateParenthesis($n) {
$result = [];$this->backtrack($result, '', 0, 0,$n);
return $result; } function backtrack(&$result, $current,$open, $close,$max) {
if (strlen($current) ===$max * 2) {
$result[] =$current;
return;
}
if ($open <$max) {
$this->backtrack($result, $current . '(',$open + 1, $close,$max);
}
if ($close <$open) {
$this->backtrack($result, $current . ')',$open, $close + 1,$max);
}
}
}