알고리즘 고득점 Kit - dfs/bfs - 타겟 넘버

문제 풀이

1. dfs bfs 둘 다 풀이가 가능하다고 생각하지만 dfs가 조금 더 쉽기도 하고 제한사항에서 숫자가 20개 이하이기 때문에 터지지 않기에 dfs를 사용하여 풀었음

2. 값들의 변경이 끝나고 숫자들의 합이 target 값이 되면 dfs 함수를 종료

3. return 값은 dfs 함수를 파고들어가서 종료 시점 기준으로 1 혹은 0 을 반환.

(dfs에 들어가는 총 합에 numbers[cnt]를 더하거나 빼서 +1인지 -1인지를 구분함)

4. 0, 0을 넣어서 함수 실행

def solution(numbers, target):
    def dfs(cnt, current_sum):
        if cnt == len(numbers):
            if current_sum == target:
                return 1
            else:
                return 0
            
        return dfs(cnt + 1, current_sum + numbers[cnt]) + dfs(cnt + 1, current_sum - numbers[cnt])
    
    return dfs(0, 0)