乘风破浪：LeetCode真题_022_Generate Parentheses
一、前言
关于括号的题目，我们已经遇到过了验证正确性的题目，现在让我们生成合法的括号列表，怎么办呢？想来想去还是递归比较方便。
二、Generate Parentheses
2.1 问题
2.2 分析与解决
既然用递归就要构造模型，这里我们定义left和right分别代表剩余的左右括号的数目，如果出现了left>right，那么就会出现实际上的左括号小于右括号的结果，出现错误，如果剩余都小于零就结束，只有都剩余为0的时候才记录，这样我们就得到了结果。
public class Solution {
public List<String> generateParenthesis(int n) {
List<String> res = new ArrayList<String>();
helper(n, n, "", res);
return res;
}
void helper(int left, int right, String out, List<String> res) {
if (left < 0 || right < 0 || left > right) return;
if (left == 0 && right == 0) {
res.add(out);
return;
}
helper(left - 1, right, out + "(", res);
helper(left, right - 1, out + ")", res);
}
}
那么官方是怎么说的呢？
class Solution {
public List<String> generateParenthesis(int n) {
List<String> combinations = new ArrayList();
generateAll(new char[2 * n], 0, combinations);
return combinations;
}
public void generateAll(char[] current, int pos, List<String> result) {
if (pos == current.length) {
if (valid(current))
result.add(new String(current));
} else {
current[pos] = '(';
generateAll(current, pos+1, result);
current[pos] = ')';
generateAll(current, pos+1, result);
}
}
public boolean valid(char[] current) {
int balance = 0;
for (char c: current) {
if (c == '(') balance++;
else balance--;
if (balance < 0) return false;
}
return (balance == 0);
}
}
也是用了一种递归的方法，先生成左括号，再递归，直至遍历完所有的情况，因此复杂度非常的高，究其原因是没有考虑到一些本来就可以省略的情况。
于是做出了改进，将一些情况进行了优化，只有右括号小于左括号的时候才能添加右括号，左括号也不能超过最大的上限：
class Solution {
public List<String> generateParenthesis(int n) {
List<String> ans = new ArrayList();
backtrack(ans, "", 0, 0, n);
return ans;
}
public void backtrack(List<String> ans, String cur, int open, int close, int max){
if (cur.length() == max * 2) {
ans.add(cur);
return;
}
if (open < max)
backtrack(ans, cur+"(", open+1, close, max);
if (close < open)
backtrack(ans, cur+")", open, close+1, max);
}
}
三、总结
这一题其实是比较难的，因为我们可能无从下手，就算用递归的时候也不能抓住要害，因此如何定义递归中变量的含义至关重要。