DA:subsetsum bruteforce

全探索（再帰関数で実装）を用いて部分和問題を解くPythonプログラム

配列numbersのいくつかの要素を取り出して，それらの和が target と同じ値になる組み合わせを見つけると，"YES"と表示するプログラムです．また，numbersの長さとその時にかかった計算時間を最後に表示します．

import time

numbers = [1, 3, 4, 5, 8]

def solve(x, i=0):
    if i == len(numbers):
        return
    if x - numbers[i] == 0:
        print("YES")
    solve(x - numbers[i], i+1)
    solve(x, i+1)

t = time.time()

W = 8
solve(W)

print('N (length of numbers):', len(numbers))
print(time.time() - t, 'sec')