def dfs(val, numbers, target, idx):
cnt = 0
if idx == len(numbers) and val == target: # 끝까지 다 계산했을 때 target값과 일치한다면
#print('yes', val)
return 1 # 경우의 수 1 리턴
elif idx == len(numbers) and val != target: # 끝까지 다 계산했는데 target값과 다르다면
#print('no', val)
return 0 # 경우의 수 0 리턴
# 두 가지 경우가 존재
cnt += dfs(val + numbers[idx], numbers, target, idx + 1) # 현재 val에 현재 idx에 해당하는 숫자를 더한 경우
cnt += dfs(val - numbers[idx], numbers, target, idx + 1) # 현재 val에 현재 idx에 해당하는 숫자를 뺀 경우
return cnt # 리턴받은 값 모두 cnt에 누적해서 리턴
def solution(numbers, target):
answer = dfs(0, numbers, target, 0) # 시작 val = 0, 시작 idx = 0로 설정
return answer