프로그래머스 타겟넘버 (python)

https://school.programmers.co.kr/learn/courses/30/lessons/43165

문제

---

주어진 숫자들을 이용해서 - + 부호를 붙여 타겟넘버를 만들면 된다. 타겟넘버를 만드는 방법 의 개수를 리턴하면 완료

입력

---

각수는 k (1 <= k <= 50) 타겟넘버는 t (1 <= t <= 1000)

출력

---

정수하나

 

cnt = 0 # 모든 방법의 수 변수

def dfs(sums,cur,numbers,target,N):
    global cnt # 전역변수 cnt
    if cur == len(numbers): # 현재 까지 더한 횟수가 정수들의 수와 같다면 즉 모두 더했다면
        if sums == target: # 현재까지 더해 저장된 수가 타겟넘버 즉 정답이면
            cnt+=1 # 방법의 수를 하나더한다.
        return # 현재 방법을 마쳤으므로 리턴
    
    dfs(sums + numbers[cur],cur + 1,numbers,target,N) # 더할때와 뺄때 각각 의 경우를 dfs로 계산한다.
    dfs(sums - numbers[cur],cur + 1,numbers,target,N)
    
def solution(numbers, target):
    answer = 0 # 정답 변수
    dfs(0,0,numbers,target,len(numbers)) # dfs(각 방법의 현재까지 더한수,현재 몇번더했는지 나타내는 수,
    									 # 정수 리스트, 타겟넘버, 정수들의 수)
    answer = cnt # 정답변수 = 모든 방법의 수 
    return answer