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 []')

Bibliography