[Level2] 타겟 넘버

🛠 문제

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

👩🏻‍💻 해결 방법

sum과 index를 가지고 bfs를 통해 문제를 해결할 수 있었다
index 값을 1씩 늘려주면서 마지막 인덱스에 도달했을 때 target인지 확인해주는 것이 문제의 핵심이었다

소스 코드

from collections import deque
def solution(numbers, target):
    answer = 0
    q = deque()
    q.append((0, 0))
    
    while q:
        sum, idx = q.popleft()
        
        if idx == len(numbers):
            if sum == target:
                answer += 1
        else:
            num = numbers[idx]
            q.append((sum + num, idx + 1))
            q.append((sum - num, idx + 1))
    
    return answer

💡 다른 사람의 풀이

answer = 0
def DFS(idx, numbers, target, value):
    global answer
    N = len(numbers)
    if(idx== N and target == value):
        answer += 1
        return
    if(idx == N):
        return

    DFS(idx+1,numbers,target,value+numbers[idx])
    DFS(idx+1,numbers,target,value-numbers[idx])
def solution(numbers, target):
    global answer
    DFS(0,numbers,target,0)
    return answer