깊이/너비 우선 탐색(DFS/BFS) 타겟 넘버

https://programmers.co.kr/learn/courses/30/lessons/43165

코딩테스트 연습 - 타겟 넘버

 

def solution(numbers, target):
    result = 0
    def dfs(num, level):
        nonlocal result
        if level == len(numbers):
            if num == target:
                result += 1
            return
        signs = [-num, num]
        if level == 1:
            for i in range(2):
                dfs(signs[i] + numbers[level], level + 1)
                dfs(signs[i] - numbers[level], level + 1)
        else:
            dfs(num + numbers[level], level + 1)
            dfs(num - numbers[level], level + 1)

    dfs(numbers[0], 1)
    return result