22-括号生成

题目描述

原题链接

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

示例 1：

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

输入：n = 1
输出：["()"]

使用简单的递归

/*
 * @lc app=leetcode.cn id=22 lang=golang
 *
 * [22] 括号生成
 */

// @lc code=start
func generateParenthesis(n int) []string {
	// 1. 递归函数的参数和返回值
	// 2. 递归函数的终止条件
	// 3. 单层搜索的过程
	var res []string

	var dfs func(left, right int, path string)
	dfs = func(left, right int, path string) {
		if left == 0 && right == 0 {
			res = append(res, path)
			return
		}

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

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

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

// @lc code=end