[프로그래머스/Python] - Lv2 / 타겟넘버

level2 - DFS - 타겟넘버

cnt = 0
def DFS(L, sum, data, target):
    global cnt
    if L == len(data): #모두 확인. 종료조건
        if sum == target:
            cnt += 1
    else: #더하거나 빼거나
        DFS(L+1, sum + data[L], data,target) #더하기
        DFS(L+1, sum - data[L], data,target) #빼기
        

def solution(numbers, target):
    DFS(0,0,numbers,target)
    return cnt

해당 문제 코멘트

백준 풀다가 프로그래머스에서 DFS풀려니 메서드에 매개변수를 너무 많이 설정해줘야 해서 버겁다. 그건 그렇고 어쨋든 전형적인 DFS문제. 부분집합으로 생각하면 쉽다. 속하냐 속하지 않느냐.
그렇게 모두 선택한 이후에 합이 sum이라면 끝 !