Implementation of a Pseudo-polynomial time solution to the Subset sum problem in Python.
from typing import List, Optional
def subset_sum(target: int, numbers: List[int]) -> Optional[List[int]]:
"""Return a subset of NUMBERS which sums to TARGET if one exists, else return None."""
def inner(progression: List[int] = [], i: int = 0) -> Optional[List[int]]:
"""TODO"""
if sum(progression) == target:
return progression
if i >= len(numbers):
return None
progression_without = inner(progression.copy(), i + 1)
if progression_without is not None:
return progression_without
progression_with = inner(progression.copy() + [numbers[i]], i + 1)
if progression_with is not None:
return progression_with
return None
return inner()
print(subset_sum(7, [2,4,5]), 'should be [2,5]')
print(subset_sum(8, [2,4,5]), 'should be None')
print(subset_sum(11, [2,4,5]), 'should be [2,4,5]')
print(subset_sum(0, [2,4,5]), 'should be []')