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:

题意

给定一个数字n，求出n个括号的正确组合方式

例子

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

题解

设定两个变量left ,right表示左右括号的个数，然后求左右括号的所有组合，其中需要排除掉一些错误的组合，当递归到left大于right时，即此时的字符串中有括号的个数大于左括号，即出现了)(这样的组合，跳过该组合。

代码

var res []string
func generateParenthesis(n int) []string {
    left:=n
    right:=n
    res = make([]string,0)
    Combine("",left,right,n*2)
    return res
}

func Combine(str string,left,right int,num int){
    
    if left>right{
        return
    }
    
    if len(str)==num{
        res = append(res,str)
        return
    }
    
    if left!=0{
        Combine(str+"(",left-1,right,num)
        if right!=0{
            Combine(str+")",left,right-1,num)
            return
        }
    }
    
    if right!=0{
        Combine(str+")",left,right-1,num)
        if left!=0{
            Combine(str+")",left-1,right,num)
            return
        }
    }
    
}

总结

一开始没好好看题目，直接写出组合的代码，结果发现是要正确的括号组合。所以这道题最重要的地方就在于，当left的剩余数量小于right时，即出现了错误的组合，因为一旦出现了一个(,即必须要有一个)与之对应，所以总是left>=right。