백준 7490번 0 만들기

https://www.acmicpc.net/problem/7490

7490번: 0 만들기

' ', '+', '-'을 조합하여 만들 수 있는 수식중에서 0이 되는것을 찾는 문제이며 문제에서 제시되는 수의 범위가 굉장히 좁기 때문에 백트래킹을 이용하여 풀어도 시간내에 해결이 되는 문제이다.

 

import sys
input = sys.stdin.readline
import copy

t = int(input())

result = []
def backtracking(i):

    global s

    if i == n:
        s += str(i)
        tmp = copy.deepcopy(s)
        tmp = tmp.replace(' ','')
        if eval(tmp) == 0:
            result.append(s)
        s = s[:-1]
        return

    s += str(i)

    for each in [' ','+','-']:
        s += each
        backtracking(i+1)
        s = s[:-1]

    s = s[:-1]


for _ in range(t):
    n = int(input())
    s = ''
    backtracking(1)
    result.append('')

for each in result:
    print(each)