1、题目链接
https://leetcode-cn.com/problems/generate-parentheses/
2、解题思路
这道题意思是给你一个数N，然后让你返回所有的包含N对括号的有效括号组合，可能有人要问了，什么是有效括号组合，看看官方的测试用例：
当N=3时：
[
"((()))",
"(()())",
"(())()",
"()(())",
"()()()"
]
估计看了也看不出个所以然来，好吧，解释一下什么是有效括号组合：
1、左括号必须用右括号闭合。
2、左括号必须以正确的顺序闭合。
总而言之，遍历整个字符串数组，当你遇到一个左括号时，把它加入一个栈中，当你遇到一个右括号时（栈中不能没有左括号），将栈中的左括号出栈，当最后数组遍历完成之后栈中没有元素，这就是一个有效的括号组合，那么我们怎么找这些有效的括号组合呢？首先一个有效的括号组合肯定是左括号开头的，这个是毫无疑问的，而且左括号和右括号是一样多的，都是N，初始状态时我们先放一个左括号，然后递归添加左右括号，那么怎么保证取到右括号的时候栈里面一定有左括号呢，任何时候左括号的数量一定是大于等于右括号的，要不然就不能保证当你取到右括号的时候栈里面一定有左括号，基于这个想法，于是就有了下面的代码：
3、代码
class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
int left = 0;
int right = 0;
if (n != 0) {
dfs(result, n, "(", "", left, right);
}
return result;
}
public void dfs(List<String> result, int n, String parentheses, String current, int left, int right) {
// 递归搜索的终止条件，左括号=右括号
if (left == right && left == n) {
// 去重
if (!result.contains(current)) {
result.add(current);
}
return;
}
// 递归搜索的终止条件，当右括号数量大于左括号数量时，不会构成有效括号对
if (left > n || right > n || right > left) {
return;
}
current += parentheses;
if (parentheses.equals("(")) {
left++;
} else {
right++;
}
dfs(result, n, "(", current, left, right);
dfs(result, n, ")", current, left, right);
}
}
4、结果
1568803187160.jpg
