22. Generate Parentheses

"""
这道题是backtrack的一道题。这道题要我们 generate all 所以一改就是递归做法。因为给的是 n pairs 所以左右括号应该各有 n 个。
我们用 l 来表示左括号的剩余个数，r 来表示或括号的剩余个数。 在递归中，如果 "(" 的剩余 > ")" 的剩余说明这是出现了不正确的解，return.
如果，l == r == 0 说明所有的括号动用完了，并且得到的是正确的解，把当前的解，append到res中。
如果以上两种都不符合：如果 l > 0, 递归求解，注意跟新参数。如果 r > 0, 递归求解。
"""

def backtrack(l, r, out, res):
    print(out)
    if l > r:
        return

    if l == 0 and r == 0:
        res.append(out)
        print("#####")
        return

    if l > 0:
        backtrack(l-1, r, out+"(", res)

    if r > 0:
        backtrack(l, r-1, out+")", res)


def generateParenthesis(n):
    res = []
    backtrack(n, n, "", res)
    return res

res = generateParenthesis(3)