프로그래머스 LV2. 타겟 넘버 (DFS)

 

여기서 문제 접근은 양수 음수 더하는 모든 경우의 수를 고려해야 하며 target값과 같아지는 경우를 세야한다는 것이다.

DFS로 양수 루트, 음수 루트로 나누어서 시행하면 풀 수 있다.

 

cnt = 0

def dfs(L, S, numbers, target):
    global cnt
    #숫자 최대 길이
    max_len = len(numbers)
    
    #만약 level이 숫자 길이만큼 도달하면
    #경우 하나 추가(target 값과 비교)
    if L == max_len:
        if S == target:
            cnt += 1
    else:
        dfs(L+1, S + numbers[L], numbers, target)
        dfs(L+1, S - numbers[L], numbers, target)

    return cnt
    
            


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