(알고리즘 공부) 타겟 넘버

n개의 음이 아닌 정수가 있습니다. 이 수를 적절히 더하거나 빼서 타겟 넘버를 만들려고 합니다. 예를 들어 [1, 1, 1, 1, 1]로 숫자 3을 만들려면 다음 다섯 방법을 쓸 수 있습니다.

-1+1+1+1+1 = 3

+1-1+1+1+1 = 3

+1+1-1+1+1 = 3

+1+1+1-1+1 = 3

+1+1+1+1-1 = 3

사용할 수 있는 숫자가 담긴 배열 numbers, 타겟 넘버 target이 매개변수로 주어질 때 숫자를 적절히 더하고 빼서 타겟 넘버를 만드는 방법의 수를 return 하도록 solution 함수를 작성해주세요.

입출력

---

numbers	target	return
[1, 1, 1, 1, 1]	3	5

 

풀이

---

def solution(numbers, target): 
    numlen = len(numbers)
    answer = 0
    
    def dfs(x, y):
        if x == numlen:
            if y == target:
                nonlocal answer 
                answer += 1
            return
        else:
            dfs(x+1, y + numbers[x])
            dfs(x+1, y - numbers[x])
    dfs(0,0)
    return answer

 

재귀함수라는 개념을 모르고 있어서 문제의 시작점조차 잡지못해 결국 풀이를 찾아보고 개념을 다시 정리했다.

 

코드가 돌아가는 순서 요약

이처럼 모든 경우의 수를 만들어서 target과 같은 값이 나오면 answer에 1을 카운트시킨다.