타겟넘버

접근 방식

처음에는 +, - 2^n만큼 경우의 수를 어떻게 구해야하나 고뇌하다가.. 어떻게 하면 BFS로 접근 가능한지 도무지 감이 안 잡히다가 힌트를 얻었다.

모든 경우의 수를 구하는 건 맞는데, 처음 시작 0에서부터 숫자 하나씩 더하기/빼기해서 트리가 확장되는 걸 떠올리면 된다!

마지막 leaf 노드들 중 target과 같은 수를 세면 끝

코드

from collections import deque

def solution(numbers, target):
    queue = deque([0])
    for n in range(len(numbers)):
        num = numbers[n]
        for _ in range(2**n):
            cur = queue.popleft()
            queue.append(cur - num)
            queue.append(cur + num)
    return queue.count(target)

여기서 중요한 부분을 뽑자면 for _ in range(2**n)일 듯..
왜 저만큼 도냐면 큐에서 하나 빼고 넣을 때마다 두배씩 큐가 확장된다.