Pythonで部分和問題

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