타겟 넘버

# numbers = [1, 1, 1, 1, 1]
# target = 3
# result = 5
numbers = [4, 1, 2, 1]	
target = 4	
# result = 2

# -1 +1 +1 +1 +1 = 3
# +1 -1 +1 +1 +1 = 3
# +1 +1 -1 +1 +1 = 3
# +1 +1 +1 -1 +1 = 3
# +1 +1 +1 +1 -1 = 3

def solution(numbers, target):
    global answer 
    answer = 0

    def dfs(idx, sumVal):
        global answer

        # print("idx = ", idx, " sumVal = ", sumVal)
        if idx == len(numbers)-1:
            if sumVal == target:
                answer += 1
                # print("Find, answer =", answer)
            return
        
            
        # print("idx = ", idx)
        dfs(idx + 1, sumVal-numbers[idx])
        dfs(idx + 1, sumVal+numbers[idx])
    
    dfs(-1,0)

    return answer

print(solution(numbers, target))

DFS 로 간단하게 풀었다.

첫 번째 항을 보자마자 값을 -1 하던 +1 하던 해줘야 하는 부분에서 어떻게 해줘야 할 지 애매했는데 그냥 제일 처음 dfs 돌 때 idx를 -1로 시작해서 첫 번째 항을 볼 때 => idx = 0 일 때부터 값을 더해주면 된다.