L2 : 타겟 넘버 Python

L2 : 타겟 넘버 Python

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

### DFS
def solution(numbers, target):
    global answer
    answer = 0
    
    def dfs(n, sum):
        global answer
        if n == len(numbers) and sum == target:
            answer += 1
        elif n < len(numbers):
            dfs(n+1, sum+numbers[n])
            dfs(n+1, sum-numbers[n])
    
    dfs(0, 0)
    return answer

### BFS
from collections import deque
def solution(numbers, target):
    answer = 0

    for a in ['+', '-']:
        dq = deque()
        if a == '+':
            dq.append([1, numbers[0]])
        else:
            dq.append([1, -(numbers[0])])
        while dq:
            cnt, s = dq.popleft()
            if cnt == len(numbers):
                if s == target:
                    answer += 1
            else:
                dq.append([cnt+1, s+numbers[cnt]])
                dq.append([cnt+1, s-numbers[cnt]])
            
    return answer

#DFS #BFS