🔥

문제

1부터 N까지의 숫자가 차례대로 적혀 있다.

수들 사이에 “+”, “-“를 넣거나 아무것도 넣지 않은 후 계산한 결과가 0이 되도록 만드려고 한다. (아무것도 넣지 않는다면 두 수는 하나의 수로 연결된다)

단, 수의 제일 앞에는 “+”, “-“가 있을 수 없다.

만약 N이 7일때는

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

과 같이 2, 3을 23으로 생각할 수 있다.

입력

양의 정수 N이 첫 줄에 입력된다.( 3 <= N <= 9 )

출력

수식을 0으로 만들 수 있는 모든 경우를 출력한다.

출력 순서는 사전순이며, 공백, +, -순서로 출력하여야 한다.

예제 1 입력

7

예제 1 출력

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

예제 2 입력

8

예제 2 출력

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

Source

n = int(input())
li = []

def dfs(x, res, tmp, form):
	# x번까지 숫자들을 사용해서 확정된 계산 결과 = res
	# 만들고 있는 수 = tmp
	# 식 = form
	# ex)
	# 1 + 2 3 - 4 5 => dfs(5, 24, -45, "1+23-45")
	# 6이 이어붙여진다면 1 + 2 3 - 4 5 6 => dfs(6, 24, -456, "1+23-456")
	# 6이 +로 붙는다면 1 + 2 3 - 4 5 + 6 => dfs(6, -21, 6, "1+23-45+6")
	# 6이 -로 붙는다면 1 + 2 3 - 4 5 - 6 => dfs(6, -21, 6, "1+23-45-6")
	if(x == n):
		result = res + tmp
		if(result == 0):
			li.append(form)
		return

	_tmp = 0
	if(tmp > 0):
		_tmp = tmp * 10 + x + 1 # 23 => 234
	else:
		_tmp = tmp * 10 - (x + 1) # -23 => -234

	dfs(x + 1, res, _tmp, form + " " + str(x + 1))
	dfs(x + 1, res + tmp, x + 1, form + "+" + str(x + 1))
	dfs(x + 1, res + tmp, -(x + 1), form + "-" + str(x + 1))

dfs(1, 0, 1, "1")
for i in range(len(li)):
	print(li[i])

참고