0022 Generate Parentheses

0022 Generate Parentheses#

Problem#

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

Examples#

Example 1:

Input: n = 3
Output: ["((()))","(()())","(())()","()(())","()()()"]

Example 2:

Input: n = 1
Output: ["()"]

Constraints#

1 <= n <= 8

Analysis#

The total combination follows the following recursive relationship:

\(T_{n} = 3T_{n-1} - 1, n>1\)

Solution#

# recursiveness: what is the complexity?
def solution(n):
    if n == 1:
        return ["()"]
    res = []
    res_inner = solution(n-1)

    for inner in res_inner:
        # append "()" + inner
        res.append("()"+inner)
        # append inner + "()"
        res.append(inner + "()")
        # append "( inner )"
        res.append("(" + inner + ")")
    # drop duplicate 
    res.remove("()"*n)
    return res

print(solution(2))
print(solution(3))
print(solution(4))

['()()', '(())']
['()()()', '(()())', '()(())', '(())()', '((()))']
['()()()()', '(()()())', '()(()())', '(()())()', '((()()))', '()()(())', '()(())()', '(()(()))', '()(())()', '(())()()', '((())())', '()((()))', '((()))()', '(((())))']
Contents