프로그래머스 - 타겟넘버 (DFS) - python

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

나의 풀이

DFS

def solution(numbers, target):
    count = 0
    def dfs(idx, total_sum):
        nonlocal count
        if idx == len(numbers):
            if total_sum == target:
                count += 1 
            return
        dfs(idx + 1, total_sum + numbers[idx])
        dfs(idx + 1, total_sum - numbers[idx])       
    dfs(0, 0)            
    return count

회고

1차 – 사실 dfs/bfs유형이 아니었다면 이게 dfs인지도 몰랐을정도로 감을 못잡았다 이것도 역시 전체 경우의 수 다 구해서 맞는것만 count하면 되는거 아닌가라는 생각은 들었는데 그걸 어떻게 구현해야할지 갑갑했다. 결국 재귀로 dfs하는 느낌으로 풀이하였다. 재귀를 여러 번 할 경우에는 트리처럼 모든 경우의 수가 점점 쪼개져서(여기서는 "+" or "-" 결과에 따라) 나눠진다는 걸 알았다.

2차 - 재귀를 쓸 때 가장 기본적인건 재귀를 실시할 때 있는 코드에 input parameter를 다시 함수 내에서(재귀 내에서) 또 정의하는 실수를 범하면 안된다. 그러면 변수가 업데이트가 안됨