Valid Parentheses

# 問題

$n$個の()を，全ての開きカッコと閉じカッコの対応が正しいように並べたときの全通りを求めよ．

# 答え

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
def valid_parentheses(n):
    ret = []
    def rec(left, right, sofar):
        if left == 0 and right == 0:
            ret.append(sofar)
            return
        if 0 < left:
            rec(left - 1, right, sofar + "(")
        if left < right:
          rec(left, right - 1, sofar + ")")
    rec(n, n, "")
    return ret

print(valid_parentheses(3))
# => ['((()))', '(()())', '(())()', '()(())', '()()()']