0 만들기

• 그냥 모든 조합을 다 시도해서 0이 되는 것들을 찾으면 된다.
• 백트래킹으로 어느정도의 가지치기를 해줄수도 있겠지만, 그런것 없이 3^(n-1)가지의 모든 경우를 다 시도해봐도 n이 작아서 돌리는데에 별 무리가 없다.
• 만들어진 각각의 식에 대해서, 결과값을 계산하는 것은 공백 연산자의 존재때문에 조금 구현이 귀찮다. 보통때에는 금기시하고 있지만, 이번에는 그냥 eval()을 사용해서 계산해버렸다.
• O(3^n)가지의 식에 대해서 계산시간이 O(n)이 걸리므로 총 시간 복잡도는 O(n*3^n)

"""Solution code for "BOJ 7490. 0 만들기".

- Problem link: https://www.acmicpc.net/problem/7490
- Solution link: http://www.teferi.net/ps/problems/boj/7490

Tags: [Brute Force]
"""

import itertools

OPER = (' ', '+', '-')


def main():
    t = int(input())
    for _ in range(t):
        N = int(input())

        s = [None] * (N + N - 1)
        s[::2] = [str(x) for x in range(1, N + 1)]
        for t in itertools.product(OPER, repeat=(N - 1)):
            s[1::2] = t
            expression = ''.join(s)
            # pylint: disable=eval-used
            if eval(expression.replace(' ', '')) == 0:
                print(expression)
        print()


if __name__ == '__main__':
    main()