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
}