16.括号的生成-回溯法

思路

递归，回溯，广度优先

右值==0时说明结束，append到组合里

右值>左值才需要右括号

(

()

() ()

() () () ()

package main

// @solution-sync:begin
func generateParenthesis(n int) []string {
	result:=make([]string,0)
	/*
	   回溯跳出条件，
	   并不需要判断左括号是否用完，因为右括号生成的条件 right > left ，
	   所以右括号用完了就意味着左括号必定用完了
	*/
	var dfs func(int, int, string)
	dfs=func(left,right int,path string){
		if right==0{
			result=append(result,path)
			return
		}
		if left>0{
			dfs(left-1,right,path+"(")
		}

		if right>left{
			dfs(left,right-1,path+")")
		}
	}
	dfs(n, n, "")

	return result
}