[Python] 타겟 넘버

✏️ 문제

 

문제 파악

이 문제도 모든 경우의 수를 다 구하는 것 같아서 dfs를 활용해 풀었다. 

이때 특징은 index가 0에서 len(number)-1가 될 때까지 다음의 값을

1. 더한다.
2. 뺀다.

로 두 가지 경우가 있으므로 dfs도 두 가지로 나누어서 돌아야 한다.

 

 

코드

def solution(numbers, target):
    answer = 0
    
    def dfs(index, total):
        nonlocal answer

        if index == len(numbers):
            if total == target:
                answer += 1
            return
        
        dfs(index + 1, total + numbers[index])
        dfs(index + 1, total - numbers[index])
    
    dfs(0, 0)
    return answer