타켓넘버
이 문제가 왜 dfs/bfs 인지 처음에는 이해가 되질 않았다.
이 포스팅이 도움이 되었다.
모든 경우의 수의 합을 트리의 맨 마지막 노드라고 생각하면,
트리의 깊이인 idx 값을 숫자 개수와 비교하여 합을 체크하면 된다.
맨 마지막 노드가 아닐 경우에는 다음 숫자를 +- 한 값을 큐에 추가한다.
큐가 모두 빌 때까지 반복한다면, 모든 자식 노드를 확인한 셈이 될 것이다.
아래는 이해를 완료한 후 다시 작성한 solution이다.
def solution(numbers, target):
answer = 0
queue = [[numbers[0], 0], [-1*numbers[0], 0]]
while queue:
temp, idx = queue.pop()
idx += 1
if idx == len(numbers):
if temp == target:
answer += 1
else:
queue.append([temp+numbers[idx], idx])
queue.append([temp-numbers[idx],idx])
return answer