프로그래머스 level2 타겟넘버

Problem

https://school.programmers.co.kr/learn/courses/30/lessons/43165?language=python3

Solution

def dfs(numbers, target, idx, sign):
    # action
    numbers[idx] = numbers[idx] * sign
    
    # end
    if idx == len(numbers) - 1:
        if sum(numbers) == target:
            return 1
        else: 
            return 0
    
    # next
    return dfs(numbers, target, idx+1, 1) + dfs(numbers, target, idx+1, -1)

def solution(numbers, target):
    return dfs(numbers, target, 0, 1) + dfs(numbers, target, 0, -1)

배열의 각 요소에 +1, -1을 곱하면서 마지막 요소까지 내려간 뒤에 합을 구하여 target과 값이 같은지를 체크하였다.

다른 사람 풀이

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)

각 요소를 양수, 음수 튜플로 만든 뒤에 itertools의 product를 이용하여 모든 경우의 수의 합을 구하였다.

Reference