프로그래머스 2단계 "타겟 넘버"

문제

프로그래머스 2단계 타겟 넘버

풀이

재귀를 이용, DFS를 구현하여 풀었다.
다음 숫자를 계산할 때 더하는 경우와 빼는 경우를 분기로 삼아 재귀를 계속하다가, 마지막 숫자의 연산이 끝날 때 타겟넘버와 연산값이 같은 경우 1을 리턴하여 결과값을 전부 더해주는 식으로 코드를 작성하였다.

Python 코드

def dfs(n, numbers, target):
  x = n + numbers[0]
  y = n - numbers[0]
  if len(numbers) == 1:
    if target == x or target == y:
      return 1
    else:
      return 0
  
  return dfs(x, numbers[1:], target) + dfs(y, numbers[1:], target)

def solution(numbers, target):
  answer = dfs(numbers[0], numbers[1:], target) + dfs(-numbers[0], numbers[1:], target)
  return answer