[Python][DFS] 프로그래머스 - 타겟 넘버(Level2)

문제출처 - https://programmers.co.kr/learn/courses/30/lessons/43165

코딩테스트 연습 - 타겟 넘버 | 프로그래머스

answer = 0
def dfs(numbers, target, idx, total):
    global answer
    
    if idx == len(numbers):
        if target == total:
            answer += 1
        return
    
    dfs(numbers, target, idx + 1, total + numbers[idx])
    dfs(numbers, target, idx + 1, total - numbers[idx])

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

설명

 

재귀 형태의 깊이우선탐색(DFS)을 사용해 풀었다.

 

answer은 전역변수로 선언했다.

 

numbers의 값들을 +/- 로 나눠 이진트리 형태로 만든 다음 모든 경우를 다 따져봐서 target이랑 일치하는 값을 찾는다.