[프로그래머스] 타겟 넘버

📕 문제

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

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

 

💡 풀이법

1. dfs, 백트랙킹을 이요해서 풀었다.

2. dfs 함수의 첫번째 인자는 현재 인덱스이고, 두번째 인자는 현재까지 계산한 값이다.

3. dfs를 돌다가 현재 계산값에서 남은 나머지 숫자를 다 빼도 target보다 크면 재귀를 멈추고, 나머지 숫자를 다 더해도 target보다 더 작으면 재귀를 멈춘다. (가지치기)

4. 현재 인덱스가 numbers의 길이(l)와 같아지면 현재 계산한 값과 target이 같을때는 ans에 +1을 하고 다르면 그냥 return 한다.

5. 앞에서 재귀가 멈추지 않았다면 인덱스를 +1해주고, 현재까지 계산한 값에 현재 인덱스에 위치한 숫자를 더해서 dfs를 돌리고, 숫자를 빼서 dfs를 돌린다.

 

def solution(numbers, target):
    l = len(numbers)
    ans = 0

    def dfs(n, num):
        nonlocal ans

        if num - sum(numbers[n:]) > target:
            return
        elif num + sum(numbers[n:]) < target:
            return

        if n == l:
            if num == target:
                ans += 1
            return

        dfs(n+1, num+numbers[n])
        dfs(n+1, num-numbers[n])

    dfs(0, 0)
    return ans