[Programmers]深度/幅優先ナビゲーション(DFS/BFS)>ターゲット番号

質問リンク

コミットコード

ver 1(for文を使用したプール-->Timeoutエラー)

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)

ver 2(再帰関数を使用したプール)

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

ver 3(他者解答)

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])