[PS] 타겟 넘버

타겟 넘버

dfs

def solution(numbers, target):
    
    def dfs(sumi, idx):
        nonlocal cnt
        
        if idx == len(numbers):
            if sumi == target:
                cnt += 1
            return
        
        num = numbers[idx]
        dfs(sumi+num, idx+1)
        dfs(sumi-num, idx+1)
        
        
    cnt = 0 
    dfs(0, 0)
    return cnt

bfs

from collections import deque

def solution(numbers, target):
    
    def bfs():
        nonlocal cnt

        while queue:
            sumi, idx = queue.popleft()

            if idx == len(numbers) :
                if sumi == target:
                    cnt += 1    
            else:    
                num = numbers[idx]
                queue.append((sumi+num, idx+1))
                queue.append((sumi-num, idx+1))

            
    queue = deque()
    queue.append((0, 0))
    cnt = 0
    bfs()
    return cnt