프로그래머스 43165. 타겟 넘버

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

프로그래머스

1. dfs 풀이

def solution(numbers, target):
    ans = 0  # 타겟 넘버를 만드는 방법의 수

    def dfs(depth, current_sum):
        nonlocal ans
        # 모든 숫자를 사용한 경우
        if depth == len(numbers):
            if current_sum == target:
                ans += 1
            return
        
        # 현재 숫자를 더하거나 빼는 두 가지 선택
        dfs(depth + 1, current_sum + numbers[idx])
        dfs(depth + 1, current_sum - numbers[idx])
    
    # DFS 탐색 시작
    dfs(0, 0)
    return ans

2. product 풀이

from itertools import product

def solution(numbers, target):
    l = [(x, -x) for x in numbers]
    s = list(map(sum, product(*l))) # product에 repeat 값 안넣어줌=기본값=1=자기자신 제외
    return s.count(target)

https://velog.io/@davkim1030/Python-%EC%88%9C%EC%97%B4-%EC%A1%B0%ED%95%A9-product-itertools

Python 순열, 조합, product - itertools

combinations 조합, 중복x

 - itertools.combinations(iterable, r)

permutations 순열, 중복o

 - itertools.permutations(iterable, r)

product 두 개 이상의 모든 리스트들의 조합

 - itertools.product(*iterables, repeat=1)