数字 n 代表生成括号的对数,请你设计一个函数,用于能够生成所有可能的并且 有效的 括号组合。用Java实现。
时间: 2024-03-16 14:43:30 浏览: 117
用java写的一个带括号的计算器
4星 · 用户满意度95%
好的,这是一个经典的括号生成问题,可以使用回溯法来解决。下面是用 Java 实现的代码:
```java
import java.util.ArrayList;
import java.util.List;
public class GenerateParentheses {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
backtrack(result, "", 0, 0, n);
return result;
}
private void backtrack(List<String> result, String current, int open, int close, int max) {
if (current.length() == max * 2) {
result.add(current);
return;
}
if (open < max) {
backtrack(result, current + "(", open + 1, close, max);
}
if (close < open) {
backtrack(result, current + ")", open, close + 1, max);
}
}
}
```
这个函数接收一个整数 n,表示生成括号的对数,返回一个 List<String>,包含所有可能的并且有效的括号组合。
在函数中,我们使用 backtrack 函数来进行回溯。回溯函数接收四个参数:结果列表 result,当前括号字符串 current,当前左括号数量 open,当前右括号数量 close,以及括号对数的最大值 max。
在回溯函数中,我们先判断当前括号字符串的长度是否达到了最大值。如果是,就将当前字符串加入结果列表中。否则,我们尝试在当前位置加上左括号或者右括号。但是需要满足以下两个条件:
1. 如果已经加入的左括号数量小于最大值,那么就可以加入左括号。
2. 如果已经加入的右括号数量小于已经加入的左括号数量,那么就可以加入右括号。
这样就可以生成所有可能的并且有效的括号组合了。
阅读全文