새싹프로그래머의 이야기

https://school.programmers.co.kr/learn/courses/30/lessons/43165

풀이방법:

• 주어진 숫자들을 모두 사용하되, 덧셈과 뺄셈을 이용해서 target과 동일한 값을 만드는 경우의 수를 구하는 문제
• dfs를 통해 모든 원소를 더한 마지막 단계부터 시작하여 이전 단계로 돌아가며 해당 단계의 원소의 값을 더했을 때와  뺐을 때의 모든 경우의 수를 탐색

풀이코드:

def solution(numbers, target):
    answer = 0
    length = len(numbers)

    def dfs(i, val):
        nonlocal answer

        if val == target and i == length - 1:
            answer += 1
            return 0

        if i + 1 < length:
            dfs(i + 1, val + numbers[i + 1])
            dfs(i + 1, val - numbers[i + 1])

    dfs(-1, 0)
    return answer