[프로그래머스 programmers] 타겟 넘버 문제풀이

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

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

dfs 문제이므로 dfs로 접근하였다.

부호는 어차피 +또는 -이기때문에 두가지 경우에 대하여 깊이탐색을 실시하고

말단 노드까지 탐색한 뒤 sum이 target과 같다면 경우의 수를 추가하는 방식.

def solution(numbers, target):

    def dfs(sum, idx):
        if idx == len(numbers):
            if sum == target:
                answer.append(1)
            return

        dfs(sum + numbers[idx],idx+1)
        dfs(sum - numbers[idx],idx+1)

    answer = []
    dfs(0, 0)
    return len(answer)