Given n pairs of parentheses,write a function to generate all combinations of well-formed parentheses.
For example,given n = 3,a solution set is:
[ “((()))”,“(()())”,“(())()”,“()(())”,“()()()” ]
java解法:
@H_301_12@public @H_301_12@class Solution {
@H_301_12@public @H_301_12@static @H_301_12@void main(String[] args) {
@H_301_12@new Solution().generateParenthesis(3);
}
@H_301_12@public List<String> generateParenthesis(@H_301_12@int n) {
backtrack(@H_301_12@new ArrayList<String>(),"",0,n);
List<String> res = @H_301_12@new ArrayList<String>();
backtrackOptmise(res,@H_301_12@new @H_301_12@char[2*n],n,0);
@H_301_12@return res;
}
@H_301_12@private @H_301_12@void backtrackOptmise(ArrayList<String> strings,@H_301_12@char[] cur,@H_301_12@int n,@H_301_12@int idx,@H_301_12@int left,@H_301_12@int right) {//通过使用char[], index的方式来优化运行速度
@H_301_12@if (idx == n * 2) {
strings.add(@H_301_12@new String(cur));
@H_301_12@return;
}
@H_301_12@if (left < n) {
cur[idx] = '(';
backtrackOptmise(strings,cur,idx + 1,left + 1,right);
}
@H_301_12@if (right < left) {
cur[idx] = ')';
backtrackOptmise(strings,left,right + 1);
}
}
@H_301_12@private List<String> backtrack(List<String> list,String str,@H_301_12@int right,@H_301_12@int max) {
@H_301_12@if (left < max) {
backtrack(list,str + "(",right,max);
}
@H_301_12@if (right < left) {
backtrack(list,str + ")",right + 1,max);
}
@H_301_12@if (str.length() == max * 2) {
list.add(str);
}
@H_301_12@return list;
}
}
golang:
func generateParenthesis(n int) []@H_301_12@string {
var strs []@H_301_12@string
backtrack(&strs,n)
return strs
}
func backtrack(strs *[]@H_301_12@string,str @H_301_12@string,right,max int ){
@H_301_12@if len(str) == max *2 {
*strs = append(*strs,str)
return
}
@H_301_12@if left < max {
backtrack(strs,max)
}
@H_301_12@if right < left {
backtrack(strs,str+ ")",right + 1,max)
}
}
相同道理,这里也可以通过byte数组进行优化;
另外,这里发现了一个关于golang值传递还是引用传递的问题,上面的代码如果参数是[]string而不是*[]string的话,会发现最终的结果res为空。事实上golang所有类型的函数参数都是传值的,不同的是,有些传递的是值本身,有些传递的是值的地址(地址本身也是值,是不可修改的)。有一篇文章说的很清晰Go语言的传参和传引用 , 因而可以结合闭包使用byte数组的方式对代码进行优化一下,提高运行速度。
@H_301_12@func generateParenthesis(n int) []string {
@H_301_12@var strs []string
@H_301_12@var gen @H_301_12@func(left,right int,buff []byte)
gen = @H_301_12@func(left,buff []byte) {
@H_301_12@if left + right == n *2 {
strs = append(strs,string(buff))
@H_301_12@return
}
@H_301_12@if left < n {
gen(left + 1,append(buff,'('))
}
@H_301_12@if right < left {
gen(left,right + 1,')'))
}
}
gen(0, 0,make([]byte,0, 2*n))
@H_301_12@return strs
}