22. Generate Parentheses --【M】Backtracking / Google / Uber / Zenefits 多练习
https://leetcode.com/problems/generate-parentheses/
好解释好思路：
http://www.cnblogs.com/grandyang/p/4444160.html
4ms 32.97% 时间O(n!) 空间O(2^n) ////
public class Solution {
public List<String> generateParenthesis(int n) {
List<String> result = new ArrayList<>();
if (n == 0)
return result;
String str = "";
dfs(result, str, n, n);
return result;
}
public void dfs(List<String> result, String str, int left, int right) {
if (left > right)
return;
if (left == 0 && right == 0) {
result.add(str);
return;
}
if (left > 0)
// str = str + "(";
dfs(result, str + "(", left-1, right);
if (right > 0)
dfs(result, str + ")", left, right-1);
}
}
*总结：
本质：给定一个数字n，让生成共有n对括号的所有正确的形式。求所有解，dfs backtracking。定义两个变量left和right分别表示剩余左右括号的个数。如果剩的左大于右，说明已经生成了不合法str, return; 如果左 和 右都等于0，说明已经完成, result.add
重点是如何递归的：如果左大于0，说明一定可以加左边，如果右大于0，一定可以加右边。
另一种思路，一样的：
如果所剩的左括号大于0，那么继续添加左括号一定是一种决策；
如果所剩的左括号少于右括号，那么补充右括号也一定是一种决策；