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

## Complexity

\(T(n)\le 2T(n-1) + O(1)\)

The solution is \(O(2^{n})\).