[Programmers] 깊이/너비 우선 탐색(DFS/BFS) > 타겟 넘버

문제링크

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

제출코드

ver1 (for문을 이용한 풀이 --> Timeout Error 발생)

def solution(numbers, target):
    tree_num = [0]
    tree = []
    for i in numbers:
        for j in tree_num:
            tree.append(i+j)
            tree.append(i-j)
        tree_num = tree
    return tree_num.count(target)

ver2 (재귀함수를 이용한 풀이)

def solution(numbers, target):
    n = len(numbers)
    target_cnt = 0
    def dfs(idx, result):
        if idx == n:
            if result == target:
                nonlocal target_cnt
                target_cnt += 1
            return 0
        else:
            dfs(idx+1, result+numbers[idx])
            dfs(idx+1, result-numbers[idx])
    dfs(0, 0)
    return target_cnt

ver3 (다른 사람 풀이)

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