括号生成
题目描述
给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。
例如,给出 n = 3,生成结果为:[
“((()))”,
“(()())”,
“(())()”,
“()(())”,
“()()()”
]
思路
看到题目就是递归呀,左括号和右括号都用完了,就将字符串添加到list中
左括号没用完就可以递归用一个左括号情况
右括号比左括号多,就可以递归用一个右括号多情况
Java实现
public List<String> generateParenthesis(int n) {
List<String> list = new ArrayList<String>();
if(n==0){
return list;
}
list = add(n,n,"",list);
return list;
}
public static List<String> add(int left, int right, String str,List<String> list){
if(left==0&&right==0){
list.add(str);
return list;
}
if(left>0){
list=add(left-1,right,str+"(",list);
}
if(right>left){
list=add(left,right-1,str+")",list);
}
return list;
}
执行用时 :4 ms, 在所有 Java 提交中击败了43.73%的用户
内存消耗 :38.7 MB, 在所有 Java 提交中击败了52.17%的用户