[프로그래머스/파이썬] 타겟 넘버

 

 

나의 풀이

from itertools import combinations

def solution(numbers, target):
    answer, minus = 0, sum(numbers) - target

    for i in range(1, len(numbers)):
        for s in combinations(numbers, i):
            if sum(s) * 2 == minus:
                answer += 1

    return answer

 

 

재귀함수를 사용한 풀이

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

 - 앞에서부터 더한 경우와 뺀경우로 나눔

 

 

 

product를 사용한 풀이

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)

 

 

 

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