[Python] 타겟 넘버

• 참고
  itertools

from itertools import product

def solution(numbers, target):
    answer = 0
    
    numbers = [(i,-1*i) for i in numbers]
    for p in list(product(*numbers)):
        if(sum(p)==target) : answer+=1
    
    return answer

others

재귀

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])

완전 탐색

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

bfs

import collections

def solution(numbers, target):
    answer = 0
    queue = collections.deque([(0, 0)])
    while queue:
        current_sum, num_idx = queue.popleft()

        if num_idx == len(numbers):
            if current_sum == target:
                answer += 1
        else:
            number = numbers[num_idx]
            queue.append((current_sum+number, num_idx + 1))
            queue.append((current_sum-number, num_idx + 1))

    return answer

dfs

answer = 0
def DFS(idx, numbers, target, value):
    global answer
    N = len(numbers)
    if(idx== N and target == value):
        answer += 1
        return
    if(idx == N):
        return

    DFS(idx+1,numbers,target,value+numbers[idx])
    DFS(idx+1,numbers,target,value-numbers[idx])

def solution(numbers, target):
    global answer
    DFS(0,numbers,target,0)
    return answer