[프로그래머스 Lv.2] 타겟 넘버 (Python)

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

프로그래머스

풀이

재귀함수를 사용한 DFS를 이용한 풀이이다.

재귀함수의 인자로는 숫자들을 사용하여 더하거나 빼기를 진행한 현재까지의 누적값이고, 다른 하나는 현재까지 더하기 또는 빼기에 사용한 숫자의 수이다.

초기값은 누적값은 0, 사용한 숫자의 수는 0으로 하였다.

종료 조건은 당연하게도 모든 숫자가 사용되었을 때, 즉 numbers 배열의 길이와 사용한 숫자의 수가 같을 때이다.

또한, 종료할 때 만약 문제에서의 조건인 누적합이 타겟 넘버와 같은 경우를 만족한다면 answer의 값을 1 증가시키게 하였다.

def solution(numbers, target):
    answer = 0 # 타겟 넘버와 누적합이 같은 경우의 수
    
    def dfs(_sum, cnt):
        nonlocal answer

        if cnt == len(numbers): # 모든 숫자를 사용하였을 때
            if _sum == target: # 누적합과 타겟 넘버가 동일하다면
                answer += 1 # 1 증가
            return # 재귀함수 종료 조건에 만족함으로 종료

		# 아직 모든 숫자를 사용하지 않았다면
		dfs(_sum + numbers[cnt], cnt + 1) # 현재 숫자를 더해주기
        dfs(_sum - numbers[cnt], cnt + 1) # 현재 숫자를 빼주기
    
    dfs(0, 0) # 초기 조건에서 재귀함수 실행
    
    return answer