XX 알고리즘 문제 2

Input: 1

Output: ["()"]

Input: 2

Output: ["(())", "()()"]

Input: 3

Output: ["((()))", "(()())", "()(())", "(())()", "()()()"]

def bfs(ans,char,l,r,n):
    global list
    # 다 썼을때
    # )가 먼저 나오면 안됨.
    if r > l: return


    # 추가 부분
    ans += char
    if char=="(":
        l+=1
        if r==n: return
    elif char==")":
        r+=1

    if l == n and r == n :
        if ans[-1]=="(": return

        list.append(ans)
        return

    if l!=n:
        ans2 = [x for x in ans] #deep copy
        bfs(ans2, "(", l, r, n)
    if r!= n:
        ans3 = [x for x in ans] #deep copy
        bfs(ans3, ")", l, r, n)

def solution(n):
    global list
    list = []
    if n<1: return "Error"
    if n==1:
        print "()",1
        return

    
    bfs([],"(",0,0,n)
    ans = []
    for row in list:
        ans.append( "".join(row) )
    print ( ans, len(ans))
solution(1)
solution(2)
solution(3)
solution(4)

() 1
(['(())', '()()'], 2)
(['((()))', '(()())', '(())()', '()(())', '()()()'], 5)
(['(((())))', '((()()))', '((())())', '((()))()', '(()(()))', '(()()())', '(()())()', '(())(())', '(())()()', '()((()))', '()(()())', '()(())()', '()()(())', '()()()()'], 14)