1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
// @Title: 括号生成 (Generate Parentheses)
// @Author: 15816537946@163.com
// @Date: 2020-06-25 07:15:36
// @Runtime: 16 ms
// @Memory: 8.2 MB
/*
 * @lc app=leetcode.cn id=22 lang=golang
 *
 * [22] 括号生成
 *
 * https://leetcode-cn.com/problems/generate-parentheses/description/
 *
 * algorithms
 * Medium (71.79%)
 * Likes:    523
 * Dislikes: 0
 * Total Accepted:    41.2K
 * Total Submissions: 57.3K
 * Testcase Example:  '3'
 *
 * 给出 n 代表生成括号的对数,请你写出一个函数,使其能够生成所有可能的并且有效的括号组合。
 * 
 * 例如,给出 n = 3,生成结果为:
 * 
 * [
 * ⁠ "((()))",
 * ⁠ "(()())",
 * ⁠ "(())()",
 * ⁠ "()(())",
 * ⁠ "()()()"
 * ]
 * 
 * 
 */
func generateParenthesis(n int) []string {
	var ans []string
	var dfs func(s string, left, right int) 
	dfs = func(s string, left, right int) {
		if left > right {
			return 
		}

		if left == 0 && right == 0 {
			ans = append(ans, s)
		}

		if left > 0  {
			dfs(s+"(", left-1, right)
		}
		if right > 0 {
			dfs(s+")", left, right-1)
		}
	}

	dfs("",n , n)
	return ans
    
}