Generate Parentheses
出处
Given n pairs of parentheses, generate all valid combinations of parentheses. E.g. if n = 2, you should return ()(), (())
Solution
解题分析:由于题目要求找出所有解,故属于发散性的DP,用backtracking。核心在于:对于当前节点,也哪些可用的选择。对本题而言:
- 如果所剩的左括号大于0,那么继续添加左括号一定是一种决策;
- 如果所剩的左括号少于右括号,那么补充右括号也一定是一种决策;
应该按照决策的选择方向进行回溯。
Complexity
可以近似认为时间复杂度为 O(n!),空间复杂度为 O(2n )
Code
void parenthesesCombination(int left, int right, String path, ArrayList<String> paths){
if (left < 0 || right < 0) return;
if (left > 0){
String newpath = path + '(';
parenthesesCombination(left-1, right, newpath, paths);
// we use newpath so as to skip the explicit backtracing
}
if (left < right){
String newpath = path + ')';
right--;
if (right == 0){
paths.add(newpath);
}
// 上面 right 已经减过了,所以不用再减
parenthesesCombination(left, right, newpath, paths);
// we use newpath so as to skip the explicit backtracing
}
}
ArrayList<String> generateParenthesis(int n){
ArrayList<String> res = new ArrayList<String>();
if (n <= 0) return res;
String path = "";
parenthesesCombination(n, n, path, res);
}