https://school.programmers.co.kr/learn/courses/30/lessons/43165
from collections import deque
def solution(numbers, target):
answer = 0
queue = deque()
n = len(numbers)
queue.append([numbers[0],0])
queue.append([-1*numbers[0],0])
while queue:
temp, idx = queue.popleft()
idx += 1
if idx < n:
queue.append([temp+numbers[idx], idx])
queue.append([temp-numbers[idx], idx])
else:
if temp == target:
answer += 1
return answer
numbers = [1, 1, 1, 1, 1] target = 3 일때
index 값을 증가시키는 이유는 numbers 리스트의 다음 숫자로 넘어갈 때마다 가능한 모든 조합을 고려하기 위함임.
numbers = [1, 2, 3]이고 target = 6인 경우
1. idx = 0, number = 1
큐 : [1, 0], [-1, 0]
2. 큐에서 [1,0]을 꺼내고 idx =1, number =2
큐: [-1,0][1+2,1] [1,-2,1]
3. 큐에서 [-1,0]을 꺼내고 idx = 1, number = 2
큐: [3,1][-1,1] [-1+2,1][-1-2,1]