[ 프로그래머스 / PYTHON ] 타겟 넘버

문제 설명

타겟넘버

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

[입출력 예]

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

알고리즘

하다가 짜증나서 다른 사람한 거 봄.

재귀를 활용한 DFS로 해결

1. dfs 함수 생성
   2. if 인덱스가 numbers의 개수와 같고, temp(지금까지 더한 값)이 target과 같다면,
      count +=1
   3. else 본래 temp에 numbers에서 다음 인덱스를 더하관 빼고,
      인덱스를 +1 해서 인덱스 알려줌 인덱스 개수가 넘어간다면 멈춰주기(return)하기 위해
2. dfs(0,0) 현재 sum = 0, 인덱스 값 = 0

코드

def solution(numbers, target):
    n= len(numbers)
    count= 0
    
    def dfs(temp, idx):
        if idx >=n:
            if temp == target: 
                nonlocal count
                count+=1
            return 
        else:
            dfs(temp+numbers[idx],idx+1)
            dfs(temp-numbers[idx],idx+1)
    
    dfs(0,0)
    return count

nonlocal 을 global로 바꾸거나 설정하지 않는다면 오류 ㄱ
[TIL / Python] 전역변수, 지역변수, 둘다아닐 때, scope 변경