[프로그래머스] 타겟 넘버

문제링크 : programmers.co.kr/learn/courses/30/lessons/43165

코딩테스트 연습 - 타겟 넘버

재귀를 통한 dfs를 이용했다. 리스트를 잘라가며 재귀에 넘겨주므로 재귀 탈출 조건으로 numbers가 빈 리스트인 경우로 설정하였다. 인자에 있는 numbers는 계산을 하기 위해 남은 숫자 리스트, sum은 현재 재귀에서의 합을 뜻한다.

그리고 입력한 숫자에 대해서 +와 -모두 고려해야 되므로 현재 sum에 -한 값과 +한 값을 sum_1, sum_2로 설정하여 이용한다.

count = 0
def dfs(numbers, target, sum):
    global count
    
    if len(numbers) == 0:
        return
    
    sum_1 = sum - numbers[0]
    sum_2 = sum + numbers[0]
    
    if len(numbers) == 1:
        if sum_1 == target:
            count += 1
        if sum_2 == target:
            count += 1
    else:
        dfs(numbers[1:], target, sum_1)
        dfs(numbers[1:], target, sum_2)    


def solution(numbers, target):
    # 2 <= len(numbers) <= 20
    global count
    dfs(numbers, target, 0)
    
    return count