백준 7490 파이썬

유형은 백트래킹 

 

T = int(input())
arr = ["+","-"," "]

def fun(N,_list):
    _list = list(_list)
    _sum = [1]
    cnt = 2
    for i in range(1,N):
        if _list[i-1] == " ":
            v = _sum.pop()
            if v > 0:
                _sum.append(v * 10 + cnt)
            else :
                _sum.append((abs(v * 10) +cnt) * -1)

        elif _list[i-1] == "-":
            _sum.append(-1* cnt)
        else: 
            _sum.append(cnt)
        cnt+= 1

    return sum(_sum)

def dfs(c,v,prv,N):
    if c == N - 1:

        if fun(N,v) == 0:
            ans = []
            for i in range(1,N+1):
                ans.append(str(i))
                if i != N:
                    ans.append(v[i-1])
            result.append(ans)
        return

    for i in range(prv,N-1):
        for j in arr:
            t = v+ j
            dfs(c+1,t,i+1,N)

for i in range(T):
    N = int(input())
    result = []
    dfs(0,"",0,N)
    result.sort()
    for i in range(len(result)):
        print("".join(result[i]))
    print()