타겟 넘버와 DFS

너무 어렵다...;;

입출력 예시

[1, 1, 1, 1, 1] target: 3
answer: 5

5가지 방법으로 1 다섯개를 가지고 3을 만들 수 있다는 뜻

def solution(numbers, target):
    def dfs(current_sum, index):
        if index == len(numbers):
            if current_sum == target:
                return 1 # 모든 수를 쓰고 target과 총합이 같음.
            return 0 # 모든 수를 썼는데 총합이 target과 같지 않으면 이 방법은 틀린 방법임.
        
        count = 0
        count += dfs(current_sum + numbers[index], index + 1)
        count += dfs(current_sum - numbers[index], index + 1)
        
        return count
    
    answer = dfs(0, 0)
    return answer

재귀 함수

• count 변수는 현재까지의 경우의 수를 나타내는 변수. 처음에는 0으로 초기화.

• 현재 숫자를 더하거나 빼서 다음 숫자를 처리하는 두 가지 경우를 모두 고려.

1. current_sum + numbers[index]: 현재까지의 합 current_sum에 현재 숫자 numbers[index]을 더한 경우를 계산
2. current_sum - numbers[index]: 현재까지의 합 current_sum에서 현재 숫자 numbers[index]을 뺀 경우를 계산

• 두 가지 경우를 모두 재귀적으로 처리하고, 그 결과를 count에 더함. 이렇게 함으로써 현재 숫자를 선택하고 더하거나 빼는 모든 가능한 경우의 수를 구할 수 있다.

이러한 재귀 호출을 통해, 최종적으로 current_sum이 target과 같다면 1을 반환하고, 아니라면 0을 반환 (base case)