[programmers/python] 타겟 넘버 - DFS

문제 요약

• numbers: 길이가 2 이상 20 이하인 양의 정수 배열
• target: 만들고자 하는 정수 (1~1000)
• 각 숫자마다 +, - 연산을 선택해서 합을 만들 수 있는 경우의 수를 구하라

---

 DFS 풀이 전략

DFS로 다음 두 가지를 매 순간 재귀적으로 선택한다:

• + numbers[i]
• - numbers[i]

def solution(numbers, target):
    def dfs(n, i):  # 누적합 n, 현재 인덱스 i
        if i == len(numbers):  # 모든 수를 다 썼다면
            return int(n == target)  # 목표값이면 1, 아니면 0
        return dfs(n + numbers[i], i + 1) + dfs(n - numbers[i], i + 1)
    
    return dfs(0, 0)

Python은 내부적으로 재귀 호출이 빠르게 처리되기 때문에, len(numbers) ≤ 20인 조건 안에서는 충분히 견딜 수 있다.

---

시간 복잡도 분석

• 각 숫자마다 +, - 두 가지 선택 → 경우의 수: 2^n
• n = 20일 때 최대 2^20 = 1,048,576
  이는 약 100만 번의 호출이며, Python에서도 1초 내외로 수행 가능하다.