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:
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× 2} × n), and the space complexity is O(n).
PythonJavaC++GoTypeScriptRustJavaScriptC#PHP
class Solution:
def generateParenthesis(self, n: int) -> List[str]:
def dfs(l: int, r: int, t: str):
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(code-box)
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) {
ans.add(t);
return;
}
dfs(l + 1, r, t + "(");
dfs(l, r + 1, t + ")");
}
}(code-box)
class Solution {
public:
vector<string> generateParenthesis(int n) {
vector<string> ans;
auto dfs = [&](this auto&& dfs, int l, int r, string t) -> void {
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;
}
};(code-box)
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
}(code-box)
function generateParenthesis(n: number): string[] {
const dfs = (l: number, r: number, t: string) => {
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 + ')');
};
const ans: string[] = [];
dfs(0, 0, '');
return ans;
}(code-box)
impl Solution {
pub fn generate_parenthesis(n: i32) -> Vec<String> {
let mut ans = Vec::new();
fn dfs(ans: &mut Vec<String>, l: i32, r: i32, t: String, n: i32) {
if l > n || r > n || l < r {
return;
}
if l == n && r == n {
ans.push(t);
return;
}
dfs(ans, l + 1, r, format!("{}(", t), n);
dfs(ans, l, r + 1, format!("{})", t), n);
}
dfs(&mut ans, 0, 0, String::new(), n);
ans
}
}(code-box)
/**
* @param {number} n
* @return {string[]}
*/
var generateParenthesis = function (n) {
const 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 + ')');
};
const ans = [];
dfs(0, 0, '');
return ans;
};(code-box)
public class Solution {
private List<string> ans = new List<string>();
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) {
ans.Add(t);
return;
}
Dfs(l + 1, r, t + "(");
Dfs(l, r + 1, t + ")");
}
}(code-box)
class Solution {
private $ans = [];
private $n = 0;
/**
* @param Integer $n
* @return String[]
*/
function generateParenthesis($n) {
$this->n = $n;
$this->ans = [];
$this->dfs(0, 0, '');
return $this->ans;
}
private function dfs($l, $r, $t) {
if ($l > $this->n || $r > $this->n || $l < $r) {
return;
}
if ($l == $this->n && $r == $this->n) {
$this->ans[] = $t;
return;
}
$this->dfs($l + 1, $r, $t . '(');
$this->dfs($l, $r + 1, $t . ')');
}
}(code-box)
