문제 설명

전체 코드

def solution(numbers, target):
    result = 0

    def dfs(i, res):
        nonlocal result
        if i == len(numbers):
            if res == target:
               result += 1
            return
        else:   
            dfs(i+1,res+numbers[i])
            dfs(i+1,res-numbers[i])

    dfs(0, 0)

    return result

해결 방법

이 문제는 전형적인 백트래킹 문제로 저번에 보았던 코딩테스트에서 나온 문제와 꽤 유사하다 (물론 코딩테스트 쪽 문제가 더 어렵게 나온다.) 이런 유형의 문제는 재귀에 대한 이해와 dfs쪽의 그래프에 대한 이해도 있어야 해서 백트래킹은 상당히 어려운 부류로 속해진다. 하지만 몇번 풀고 이해하려고 노력하면 상당히 정형화 되어있는 문제이기도 하다.

먼저 이 문제에서는 백트래킹에 알맞게 목표를 정해주어야 한다. 따라서 재귀를 하였을때 i를 0부터 시작하여 len(numbers)와 같아졌을때 return을 하는데 이때 지금까지 구한 값이 target과 같다면 result에 +1을 해준다. 만약 i가 len(numbers)와 같지 않았을때는 어차피 문제에서 더하기와 빼기만 고려하라 하였으므로 res라는 값에 재귀적으로 +1와 -1을 해준다. 그 후 초기값을 0,0 으로 시작하면 문제는 쉽게 풀린다. 만약 말로 이해가 안된다면 꼭 디버깅을 해보길 추천한다.