数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合,请给出java代码
时间: 2024-02-09 12:09:22 浏览: 55
Latex公式常见符号.pdf
5星 · 资源好评率100%
这是一个经典的回溯算法问题,可以按照以下思路来解决:
1. 定义一个列表来存储所有有效的括号组合。
2. 定义一个回溯函数backtrack,它包含当前组合、左括号的数量和右括号的数量三个参数。
3. 如果左右括号的数量都等于n,将当前组合添加到列表中。
4. 如果左括号的数量小于n,则可以添加左括号,并递归调用backtrack函数。
5. 如果右括号的数量小于左括号的数量,则可以添加右括号,并递归调用backtrack函数。
下面是完整的Java代码实现:
```
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<>();
backtrack(res, "", 0, 0, n);
return res;
}
private void backtrack(List<String> res, String curr, int left, int right, int n) {
if (left == n && right == n) {
res.add(curr);
return;
}
if (left < n) {
backtrack(res, curr + "(", left + 1, right, n);
}
if (right < left) {
backtrack(res, curr + ")", left, right + 1, n);
}
}
```
注意:在这段代码中,回溯函数backtrack的三个参数分别表示当前组合、左括号的数量和右括号的数量。在backtrack函数中,首先判断左右括号的数量是否都等于n,如果是,则将当前组合添加到列表中;否则,如果左括号的数量小于n,则可以添加左括号,并递归调用backtrack函数;如果右括号的数量小于左括号的数量,则可以添加右括号,并递归调用backtrack函数。
阅读全文