[프로그래머스 lv2] 타겟 넘버 - 파이썬(Python)

문제

프로그래머스

풀이

1. 재귀함수 이용

def recursive(numbers, target, summ):
  if numbers == []:
    if summ == target:
      return 1
    else:
      return 0
  return recursive(numbers[1:], target, summ + numbers[0]) + recursive(numbers[1:], target, summ - numbers[0])

def solution(numbers, target):
  return recursive(numbers, target, 0)

2. DFS 이용

def solution(numbers, target):
  global answer
  answer = 0
  
  def dfs(i, summ):
    if i == len(numbers):
      if summ == target:
        global answer 
        answer += 1
      return
    dfs(i+1, summ + numbers[i])
    dfs(i+1, summ - numbers[i])

  dfs(0,0)
  return answer

3. BFS 이용

def solution(numbers, target):
  summ = [0]
  answer = 0
  for n in numbers: 
    cur = []
    for s in summ:
      cur.append(s + n)
      cur.append(s - n)
    summ = cur
  for s in summ : 
    if s == target : 
      answer += 1
  return answer

4. 중복 순열 product 라이브러리 이용

from itertools import product
def solution(numbers, target):
    l = [(n, -n) for n in numbers]
    s = list(map(sum, product(*l)))
    return s.count(target)