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

문제 링크

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

문제 설명

• 주어진 numbers의 배열에서 +, -를 사용해서 target 넘버도 주어진 숫자와 같은 경우의 수를 구하는 문제이다.
• 재귀를 사용해서 숫자 앞에 부호가 +, -일때 모든 경우의 수를 구하면 다음과 같다.
• 파이썬은 함수 사용시에 리스트를 인자로 넘겨주지 않아도 접근 가능했는데 프로그래머스에서는 다른 함수내에서 사용 하려면 인자로 넘겨주어야 한다.

코드

def solution(numbers, target):
    answer = dfs(0, numbers, target)
    return answer

def dfs(step, numbers, target):
    answer = 0
    
    if step == len(numbers):
        if sum(numbers) == target:
            return 1
        else:
            return 0
    else:
        answer = answer + dfs(step + 1, numbers, target)
        numbers[step] = - numbers[step]
        answer = answer + dfs(step + 1, numbers, target)
    
    return answer