[Python3]프로그래머스_타겟 넘버

문제출처:https://programmers.co.kr/learn/courses/30/lessons/43165?language=python3

접근법

전형적인 DFS 문제인 것같다.
1. numbers 배열의 index를 증가시키면서 재귀함수를 호출한다.
2. 재귀함수의 index가 k일때 리스트의 k번째 숫자를 음수일 때,양수일 때를 나눠 재귀함수를 호출한다.
3. 더 이상 계산할 index가 없을 때 현재 리스트의 합이 target과 같으면 정답에 추가한다.

+ 변수 앞에 global을 붙이면 전역변수를 함수 내에서 사용할 수 있다.

코드

def dfs(l,index):
    global ans,num
    if( index == len(l) ):
        if( sum(l) == num ): 
            ans += 1
        return
    dfs(l,index+1)
    l[index] = -l[index]
    dfs(l,index+1)

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