[Programmers ] Lv2. 타겟 넘버

문제

바로가기

코딩테스트 연습 - 타겟 넘버

 

풀이

• dfs함수를 통해 인덱스를 증가시키면서 2번의 재귀를 진행(-, +)하고, 만약 idx가 배열의 끝까지 진행되어서 원하는 값이 나왔다면 answer에 추가

 

코드

answer = 0

def dfs(numbers, target, idx, sum):
    global answer
    if idx == len(numbers):
        if sum == target:
            answer += 1
        return
    dfs(numbers, target, idx+1, sum+numbers[idx])
    dfs(numbers, target, idx+1, sum-numbers[idx])

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