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

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43165

프로그래머스

코드

def solution(numbers, target):
	cnt = 0
    size = len(numbers)
    def dfs(depth,total):
        if depth == size:
            if total == target:
                nonlocal cnt
                cnt += 1
            return 
        dfs(depth+1,total+numbers[depth])
        dfs(depth+1,total-numbers[depth])
    dfs(0,0)
    return cnt

풀이

• DFS로 해결했다.
• depth가 len(numbers) 되면, 그때까지의 total이 target과 같을 경우 cnt를 1 증가시켜준다.
• 주의할 점은 뎁스가 증가할때, 둘 중 하나를 더하고, 안 더하고가 아닌, 둘다 더하거나 빼야 된다는 점이다.