[코딩테스트] 타겟 넘버 with Python

아이디어

DFS 문제이다.
예를 들어numbers : [ 1, 1, 1 ],target : 1이 들어왔다면 아래와 같은 이진 트리 구조를 갖는다.

노드의 종점에서 target 값과 비교해 같다면 answer에 +1을 해주는 것이다.

문제 풀이 코드

def solution(numbers, target):
    answer = 0
    def dfs(current_total, current_index, sign): # dfs(0,0,1)
        nonlocal answer

        current_total += numbers[current_index] * sign 

        if len(numbers) <= current_index + 1: # 1
            if current_total == target:
                answer += 1
        else: # 2
            dfs(current_total, current_index + 1, 1)
            dfs(current_total, current_index + 1, -1)
        return

    dfs(0,0,1)
    dfs(0,0,-1)
    return answer

#1

다음 인덱스가 존재하지 않을 때 (노드의 종점일때 )

#2

다음 인덱스가 존재 할 때 (노드의 종점이 아닐 때)