https://programmers.co.kr/learn/courses/30/lessons/43165?language=python3
DFS
풀이
def solution(numbers, target):
if not numbers and target == 0 :
return 1
elif not numbers:
return 0
else:
return solution(numbers[1:], target-numbers[0]) + solution(numbers[1:], target+numbers[0])
다른사람의 풀이입니다
BFS
풀이
import collections
def solution(numbers, target):
answer = 0
stack = collections.deque([(0, 0)])
while stack:
print(stack)
current_sum, num_idx = stack.popleft()
print(current_sum , num_idx)
if num_idx == len(numbers):
if current_sum == target:
answer += 1
else:
number = numbers[num_idx]
stack.append((current_sum+number, num_idx + 1))
stack.append((current_sum-number, num_idx + 1))
return answer
print(solution([1,1,1,1,1,] , 3))