프로그래머스. 깊이/너비 우선 탐색(DFS/BFS). 타겟 넘버 파이썬 풀이

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

Level 2

프로그래머스. 깊이/너비 우선 탐색(DFS/BFS). 타겟 넘버 파이썬 풀이

count = 0

def dfs(index, numbers, number, target):
    global count

    # 다음 인덱스가 없다면
    if (index + 1) == len(numbers):
        # target과 현재 수 number를 비교하여 같다면 카운트 1 증가
        if target == number:
            count += 1
            return
    # 다음 인덱스가 있다면 다음 수를 +하는 경우와 -하는 경우 dfs
    else:
        dfs(index + 1, numbers, number + numbers[index + 1], target)
        dfs(index + 1, numbers, number - numbers[index + 1], target)


def solution(numbers, target):
    global count

    dfs(0, numbers, numbers[0], target)
    dfs(0, numbers, -numbers[0], target)

    return count