sum 계산시

Question

def DFS(L, sum):

global res

if L > res: ## Cut Edge

return

if sum > m:

return

if sum == m:

if L < res:

res = L

else:

for i in range(n):

sum += a[i]

DFS(L+1, sum)

안녕하세요! 문제 풀다가 궁금한 점이 생겨 질문드립니다.

sum을 넘겨줄때 DFS(L+1, sum + a[i])가 아닌 위 하늘색 부분처럼 미리 계산해서 넘겨주면 결과가 다르게 나오던데 제 눈에는 같아 보여서요...! 결과가 달라지는 이유가 궁금합니다.

Answer

안녕하세요^^

for i in range(n):

sum += a[i]

DFS(L+1, sum)

위와 같이 재귀를 호출하기 전에 sum에 미리 더해주면 백을 해서 되돌아 왔을 때 원래 sum값으로 되돌아와 다른 경우를 해야 하는데 sum에 a[i]가 더해진 값으로 되돌아 옵니다. 그래서

for i in range(n):

sum += a[i]

DFS(L+1, sum)

sum -= a[i]

처럼 재귀호출 아래에서 sum에서 a[i]값을 빼주어야 합니다.