문제

1부터 N까지의 수를 오름차순으로 쓴 수열 1 2 3 ... N을 생각하자.

그리고 '+'나 '-', 또는 ' '(공백)을 숫자 사이에 삽입하자(+는 더하기, -는 빼기, 공백은 숫자를 이어 붙이는 것을 뜻한다). 이렇게 만든 수식의 값을 계산하고 그 결과가 0이 될 수 있는지를 살피자.

N이 주어졌을 때 수식의 결과가 0이 되는 모든 수식을 찾는 프로그램을 작성하라.

입력

첫 번째 줄에 테스트 케이스의 개수가 주어진다(<10).

각 테스트 케이스엔 자연수 N이 주어진다(3 <= N <= 9).

출력

각 테스트 케이스에 대해 ASCII 순서에 따라 결과가 0이 되는 모든 수식을 출력한다. 각 테스트 케이스의 결과는 한 줄을 띄워 구분한다.

1+2-3+4-5-6+7
1+2-3-4+5+6-7
1-2 3+4+5+6+7
1-2 3-4 5+6 7
1-2+3+4-5+6-7
1-2-3-4-5+6+7

풀이

1. 위와같이 1~7 까지의 수의 중간에 +,-,빈칸 이 들어가게 됩니다.
2. 그 값이 0 이 되는 식을 모두 출력하는 문제입니다.
3. ADD 함수 : 기존의 숫자 리스트에 ['+','-',' '] 의 값을 하나씩 모두 넣는 함수입니다 .
   • 1,2,3 => [1+2+3, 1+2-3, 1+2 3, 1-2+3, 1-2-3, 1-2 3, 1 2+3, 1 2-3,1 2 3]
4. 이제 이 값들을 계산하기 쉽게 바꿔줍니다
   • 빈칸 제거 " " => ""
   • '+' 로 나누려고 하는데 -의 값이 신경이 쓰입니다.
   • '-' 값을 '+-' 로 바꿔줍니다 => 3 + 5 - 3 => 3+ 5 +(-3) 이 되게끔 바꿔줍니다.(핵심)

T = int(input())
symbols = ['+','-',' ']

def ADD(time,message):
    if len(message) == 2*N -1:
        everynums.append(message)
        return
    else:
        for symbol in symbols:
            message2 = message + symbol + str(numlist[time])
            ADD(time+1,message2)

for tc in range(T) :
    N = int(input())
    numlist = list(range(1,N+1))
    everynums = []
    ADD(1,str(numlist[0]))
    result =[]
    for num in everynums:
        nnum = num.replace(" ","")
        nnum = nnum.replace("-","+-")
        newnum = nnum.split("+")

        check = 0
        for i in newnum:
            check += int(i)
        if check ==0:
            result.append(num)
    result = sorted(result)

    for r in result:
        print(r)

    print()