22.Generate Parentheses

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解法：

public class Solution {
    public static void main(String[] args) {
        new Solution().generateParenthesis(3);
    }

    public List<String> generateParenthesis(int n) {
        backtrack(new ArrayList<String>(),"",0,n);
        List<String> res = new ArrayList<String>();
        backtrackOptmise(res,new char[2*n],n,0);
        return res;
    }

    private void backtrackOptmise(ArrayList<String> strings,char[] cur,int n,int idx,int left,int right) {//通过使用char[]， index的方式来优化运行速度
        if (idx == n * 2) {
            strings.add(new String(cur));
            return;
        }
        if (left < n) {
            cur[idx] = '(';
            backtrackOptmise(strings,cur,idx + 1,left + 1,right);
        }
        if (right < left) {
            cur[idx] = ')';
            backtrackOptmise(strings,left,right + 1);
        }

    }

    private List<String> backtrack(List<String> list,String str,int right,int max) {
        if (left < max) {
            backtrack(list,str + "(",right,max);
        }
        if (right < left) {
            backtrack(list,str + ")",right + 1,max);
        }
        if (str.length() == max * 2) {
            list.add(str);
        }
        return list;
    }
}

golang：

func generateParenthesis(n int) []string {
    var strs []string
    backtrack(&strs,n)
    return strs
}

func backtrack(strs *[]string,str string,right,max int ){
    if len(str) == max *2 {
        *strs = append(*strs,str)
        return
    }
    if left < max  {
        backtrack(strs,max)
    }
    if right < left {
        backtrack(strs,str+ ")",right + 1,max)
    }
}

相同道理，这里也可以通过byte数组进行优化；
另外，这里发现了一个关于golang值传递还是引用传递的问题，上面的代码如果参数是[]string而不是*[]string的话，会发现最终的结果res为空。事实上golang所有类型的函数参数都是传值的，不同的是，有些传递的是值本身，有些传递的是值的地址（地址本身也是值，是不可修改的）。有一篇文章说的很清晰Go语言的传参和传引用 ， 因而可以结合闭包使用byte数组的方式对代码进行优化一下，提高运行速度。

func generateParenthesis(n int) []string {
    var strs []string
    var gen func(left,right int,buff []byte)
    gen = func(left,buff []byte) {
        if left + right == n *2 {
            strs = append(strs,string(buff))
            return
        }
        if left < n {
            gen(left + 1,append(buff,'('))
        }
        if right < left {
            gen(left,right + 1,')'))
        }
    }
    gen(0, 0,make([]byte,0, 2*n))
    return strs
}