Pythonで部分和問題
# coding=utf-8 # 部分和問題 # 深さ優先検索 # 整数がn個与えられる。その中からいくつか選び、その環をちょうどkにすることができるかどうかを判定する def solve(integer_list, target_sum, i=0, sum=0): if i == len(integer_list): return sum == target_sum if (solve(integer_list, target_sum, i + 1, sum)): return True if (solve(integer_list, target_sum, i + 1, sum + integer_list[i])): return True return False # n個の整数 integer_list = [1,3,5,12,7] # k target_sum = 11 print solve(integer_list, target_sum) # => True