[Level 2] 타겟 넘버

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

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

---

접근

전달받은 numbers의 숫자들을 더하거나 빼서 target을 만들 수 있는 경우의 수가 몇 개인지 구해야한다. 따라서 DFS를 통해 모든 경우의 수를 먼저 구했다. 

 

구현

- DFS 내에서 현재 인덱스와 지금까지 합을 더하거나 뺄 때로 나눠서 재귀호출을 진행하였고

- idx가 N이 될 때는 모든 선택이 된 것이기 때문에 지금까지 더한 것이 target과 같을 때 

- 최종해를 더해주었다.

def solution(numbers, target):
    answer = 0
    N = len(numbers)

    def dfs(idx, total):
        nonlocal answer
        if idx == N:
            if total == target:
                answer += 1
            return
        dfs(idx+1, total + numbers[idx])
        dfs(idx+1, total - numbers[idx])

    dfs(1, -numbers[0])
    dfs(1, numbers[0])
    return answer