Subset Sum

Given a set \(X\) of positive integers, can you find a subset that sums to \(T\)?

The general idea is that you have two choices: Either pick a particular number and see if you can solve the \(T-x\) case, or don’t pick it and see if you can get \(T\) without \(x\):

def subset_sum(numbers, target, index):
    if target == 0:
        return True
    if target < 0 or index == 0:
        return False
    x = numbers[index]
    if subset_sum(numbers, target - x, index - 1):
        return True
    if subset_sum(numbers, target, index - 1):
        return True
    return False