[Baekjoon] 7490. 0 만들기 - python

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

7490번: 0 만들기

설계 방법

재귀

sum : 현재까지의 연산값

sign : 다음 연산에 num과 함께 들어갈 연산자(+는 1로, -는 -1로 표현, 빈칸이 들어갈떄는 무의미함)

num : 다음에 연산될 숫자

n : 몇번째 항인지를 나타냄

string : 현재까지의 표현식

코드

 

def recur(sum, sign, num, n, string):
  if (n == N):
    sum = sum + (sign*num)
    if sum == 0:
      print(string)
  else:
    recur(sum ,sign ,num*10+(n+1), n+1, string+' '+str(n+1))
    recur(sum+sign*num ,1 ,(n+1), n+1, string+'+'+str(n+1))
    recur(sum+sign*num, -1, (n+1), n+1, string+'-'+str(n+1))
      
test_case = int(input())

for _ in range(test_case):
  N = int(input())
  recur(0,1,1,1,"1")
  print()

 

참고 : https://velog.io/@tks7205/%EB%B0%B1%EC%A4%80-7490-0%EB%A7%8C%EB%93%A4%EA%B8%B0backtracking