22 Generate Parentheses

https://leetcode.com/problems/generate-parentheses/

solution

• dfs: 回溯从多叉树的角度理解，每个位置都试图增加左括号或右括号

class Solution:
    def generateParenthesis(self, n: int) -> List[str]:
        path = []
        res = []
        self.dfs(0, 0, n, path, res)
        return res

    def dfs(self, left: int, right:int, n: int, path: List, res: List):
        if len(path) == 2 * n:
            res.append(''.join(path))
            return

        if left < n:  # 左右条件是关键, 普通回溯模版里可能是通过for循环逐个加，但括号只分别考虑左和右
            path.append('(')
            self.dfs(left + 1, right, n , path, res)
            path.pop()  # 这里，为什么在加入右上面就pop. 类似把一般回溯for循环的多个条件分开写

        if right < left:
            path.append(')')
            self.dfs(left, right + 1, n , path, res)
            path.pop()

时间复杂度：O(4^n / sqrt(n)) 空间复杂度：O(n)

def generateParenthesis(self, n: int) -> List[str]:
	def dfs(left, right, s):
		if len(s) == n * 2:
			res.append(s)
			return 

		if left < n:
			dfs(left + 1, right, s + '(')

		if right < left:
			dfs(left, right + 1, s + ')')

	res = []
	dfs(0, 0, '')
	return res

follow op

括号类小结

95. Unique Binary Search Trees II