一、简介

数字 n 代表生成括号的对数，请你设计一个函数，用于能够生成所有可能的并且 有效的 括号组合。

输入：n = 3
输出：["((()))","(()())","(())()","()(())","()()()"]

题目地址：leetcode

二、实现

func generateParenthesis(n int) []string {
    if n == 0 {
        return nil
    }
    
    if n == 1 {
        return []string{"()"}
    }

    res := make([]string, 0)
    doGenerateParenthesis(&res, []byte{}, []byte{}, n)

    return res
}

// 思路：每次可以选择'('，也可以选择')'。当选择'('的时候，需要往')'队列中新增一个，且n--；当选择')'的时候，n的大小不变
// res 代表结果
// curList 有效括号组成的字符数组
// 待使用'('组成的数组
// n 待使用的括号对数
func doGenerateParenthesis(res *[]string, curList, rightFlags []byte, n int) {
    if n == 0 && len(rightFlags) == 0 {
        b := make([]byte, len(curList))
        copy(b, curList)

        *res = append(*res, string(b))

        return
    } 

    if n > 0 {
        // 添加 （
        rightFlags = append(rightFlags, ')')
        curList = append(curList, '(')

        doGenerateParenthesis(res, curList, rightFlags, n-1)

        // 回溯, 添加 )
        if len(rightFlags) > 1 {
            rightFlags = rightFlags[:len(rightFlags) -2]
            curList = curList[:len(curList) -1]
            curList = append(curList, ')')

            doGenerateParenthesis(res, curList, rightFlags, n)
        }
    } else if len(rightFlags) > 0 {
        rightFlags = rightFlags[:len(rightFlags) -1]
          curList = append(curList, ')')
        doGenerateParenthesis(res, curList, rightFlags, n)
    }
}