当前位置： 面试刷题>> 生成括号 (经典算法题500道)
**题目描述**：
给定一个整数n（n >= 0），请你生成并返回所有由n对括号(`(`和`)`)组成的、并且有效的括号组合。
例如，输入n = 3时，输出应该是：
```
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
```
**解题思路**：
这个问题可以使用回溯法（也称为深度优先搜索DFS）来解决。我们可以定义一个递归函数来尝试在字符串的每个位置添加左括号或右括号，但要确保在任何时候左括号的数量都不少于右括号的数量，并且在最终生成的字符串中左括号和右括号的总数都为n个。
**PHP代码示例**：
```php
function generateParenthesis($n) {
$result = [];
backtrack($result, '', 0, 0, $n);
return $result;
}
function backtrack(&$result, $current, $open, $close, $max) {
if (strlen($current) == $max * 2) { // 当字符串长度为2n时，完成一个组合
$result[] = $current;
return;
}
if ($open < $max) { // 尝试添加一个左括号
backtrack($result, $current . '(', $open + 1, $close, $max);
}
if ($close < $open) { // 确保右括号数量小于左括号数量时，添加右括号
backtrack($result, $current . ')', $open, $close + 1, $max);
}
}
// 示例调用
echo json_encode(generateParenthesis(3));
```
**Python代码示例**：
```python
def generateParenthesis(n):
def backtrack(s, open, close, result):
if len(s) == 2 * n:
result.append(s)
return
if open < n:
backtrack(s + '(', open + 1, close, result)
if close < open:
backtrack(s + ')', open, close + 1, result)
result = []
backtrack("", 0, 0, result)
return result
# 示例调用
print(generateParenthesis(3))
```
**JavaScript代码示例**：
```javascript
function generateParenthesis(n) {
const result = [];
function backtrack(current, open, close) {
if (current.length === 2 * n) {
result.push(current);
return;
}
if (open < n) {
backtrack(current + '(', open + 1, close);
}
if (close < open) {
backtrack(current + ')', open, close + 1);
}
}
backtrack("", 0, 0);
return result;
}
// 示例调用
console.log(JSON.stringify(generateParenthesis(3)));
```
**码小课分享**：
码小课网站中分享了更多关于算法和数据结构的学习内容，包括但不限于回溯法、动态规划、图论等，帮助你系统地掌握编程技能，提升编程能力。欢迎访问码小课网站，与更多编程爱好者一起学习和交流。