[PRO] 타겟 넘버 (Python) [알고리즘 고득점 Kit]

문제

https://school.programmers.co.kr/learn/courses/30/lessons/43165

풀이

문제에서 주어진 n이 2~20이므로 시간복잡도 2^n도 통과를 한다. 따라서 모든 경우의 수에 대해 생성을 해서 확인하도록 했다.

itertools의 product를 이용해서 아래와 같이 풀이했다.

from itertools import product

def solution(numbers, target):
    answer = 0
    n = len(numbers)
    
    for sings in product([1,-1],repeat=n):
        if sum(n*s for n,s in zip(numbers,sings)) == target:
            answer+=1
    
    return answer