22.括号的生成

题目描述

给出 n 代表生成括号的对数，请你写出一个函数，使其能够生成所有可能的并且有效的括号组合。

例如，给出 n = 3，生成结果为：

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

思路

1.这道题可以使用回溯算法求解。
2.我们需要三个变量记录当前执行状态，leftNum记录左括号的个数，rightNum记录右括号的个数，n记录括号的对数。
3.我们递归的思路就是，若左括号没达到上限则拼接左括号，否则拼接右括号；若字符串长度达成了标准（n*2），则表明这是一个解，将其加入集合后，进行回溯。

Java代码实现

public List<String> generateParenthesis(int n) {
        List<String> res = new ArrayList<>();
        generateParenthesis(n,0,0,res,"");
        System.out.println(res);
        return res;
    }

private void generateParenthesis(int n,int leftNum,int rightNum,List<String> res,String cur){
        if(cur.length() == n*2){
            res.add(cur);
            return;
        }
        if(leftNum < n)
            generateParenthesis(n,leftNum+1,rightNum,res,cur+"(");
        if(rightNum < leftNum)
            generateParenthesis(n,leftNum,rightNum+1,res,cur+")");
    }

Golang代码实现

func generateParenthesis(n int) []string {
    res := make([]string,0)
    if n == 0 {
        return res
    }

    generateParenthesisBackTrace(n,0,0,"",&res)

    return res
}

func generateParenthesisBackTrace(n int,left int,right int,cur string,res *[]string) {
    if len(cur) == n*2{
        *res = append(*res,cur)
        return
    }

    if left < n{
        generateParenthesisBackTrace(n,left+1,right,cur+"(",res)
    }

    if right < left{
        generateParenthesisBackTrace(n,left,right+1,cur+")",res)
    }
}