[프로그래머스] 타겟넘버 (python 파이썬)

재귀 문제이다. 

dfs로 문제를 풀었다.

한 숫자에 대해서 양수 or 음수를 더할수 있다.

마지막 depth에 도달했을때 target과 같으면 count 를 증가시킨다.

 

count = 0
def solution(numbers, target):
    dfs(numbers, target, 0, 0)   
    return count

def dfs(numbers, target, depth, result):
    global count
    if depth == len(numbers):
        if result == target:
            count += 1
        return
    
    left = result - numbers[depth]
    right = result + numbers[depth]
    
    dfs(numbers, target, depth+1, left)
    dfs(numbers, target, depth+1, right)