讨论/《深度优先搜索》 - 练习:括号生成/
《深度优先搜索》 - 练习:括号生成
共 2 个回复
func generateParenthesis(n int) []string {
	result := []string{}
	var dfs func(l, r int, path string) // 左括号剩余个数、右括号剩余个数
	dfs = func(l, r int, path string) {
		if l == 0 && r == 0 {
			result = append(result, path)
			return
		}

		if l > 0 {
			path = path + "("
			dfs(l-1, r, path)
			path = path[:len(path)-1]
		}
		if r > 0 && r > l {
			path = path + ")"
			dfs(l, r-1, path)
		}
	}
	dfs(n, n, "")
	return result
}

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        ans = []
        def dfs(pth, L, R):
            if not L and not R:
                ans.append(''.join(pth))
            else:
                if L :
                    dfs(pth + ['('], L-1, R)
                if R > L :
                    dfs(pth + [')'], L, R-1)
        dfs([], n, n)
        return ans