问题：
Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
官方难度：
Medium
翻译：
合并n个括号，生成所有n个括号组成的合理序列。
例子：
给定n=3，解集为
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
方法一：
- 初始的思想，考虑使用递归，每次优先获取n-1个括号所有情况下的集合，然后插入新的括号。
- 递归的终点是n=1，返回包含一个元素“()”的集合。
- 每次先加“(”，在第一个位置和一个“)”的下一个位置，插入左括号。
- 然后加右括号，从加入的左括号开始，统计左括号和右括号的个数，在左括号个数大于右括号个数的情况下，才可以加入右括号。
- 不难发现，虽然已经极力避免了，但是这种方法会出现很多的重复情况，所以需要一个Set集合去重，在递归结束之后，转化成List集合返回。
方法一的解题代码：
// 根据n-1的情况增加括号
public static List<String> method(int n) {
List<String> list = new ArrayList<>(getPharentheses(n));
return list;
} private static Set<String> getPharentheses(int n) {
Set<String> set = new HashSet<>();
if (n == 1) {
set.add("()");
} else {
Set<String> last = getPharentheses(n - 1);
for (String s : last) {
String s1 = "(" + s;
int l1 = 0;
int r1 = 0;
for (int j = 1; j < s1.length(); j++) {
if (s1.charAt(j) == '(') {
l1++;
} else {
r1++;
}
// 这里有重复的可能性
if (l1 > r1) {
set.add(s1.substring(0, j + 1) + ")" + s1.substring(j + 1));
}
}
// 先加左括号
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == ')') {
String str = s.substring(0, i + 1) + "(" + s.substring(i + 1);
// 左右括号计数
int l = 0;
int r = 0;
for (int j = i + 1; j < str.length(); j++) {
if (str.charAt(j) == '(') {
l++;
} else {
r++;
}
// 这里有重复的可能性
if (l > r) {
set.add(str.substring(0, j + 1) + ")" + str.substring(j + 1));
}
}
}
}
}
}
return set;
}
method
方法二：
- 显而易见，如果通过某种算法，没有重复的情况产生，那么方法的执行效率一定会快很多。
- 假设n=3。先加上所有的左括号，“(((”，那么右括号的可能性只有一个，那就是“((()))”。
- 然后回退一步，少加一个左括号，加上一个右括号，之后再加上这个左括号，会形成以下形式“(()())”。
- 后加的左括号再回退一步“(())()”。依次类推，直到这个左括号不能再加为止，回退至第一步，在一开始回退2个左括号，得到以下2种形式“()(())”和“()()()”。
- 发现回退的左括号为n时，结束。
- 解题的代码形式很简单，但是逻辑比较难捋通顺。
- 注意入参检查。
方法二的解题代码：
public static List<String> generateParenthesis(int n) {
if (n < 1) {
throw new IllegalArgumentException("Input error");
}
List<String> list = new ArrayList<>();
generate(n, n, "", list);
return list;
}
// 先加所有左括号，遍历所有可能性，然后回退一个左括号，依次类推
private static void generate(int left, int right, String current, List<String> list) {
// 先加左括号
if (left > 0) {
generate(left - 1, right, current + "(", list);
}
if (right > 0 && right > left) {
generate(left, right - 1, current + ")", list);
}
if (left == 0 && right == 0) {
list.add(current);
}
}
generateParenthesis
相关链接：
https://leetcode.com/problems/generate-parentheses/
PS：如有不正确或提高效率的方法，欢迎留言，谢谢！