Dynamic programming algorithm for subset sum

subset_sum.py

"""Two tricks enable an efficient solution:
2. We can solve the problem for the first i numbers in the list, for
   i = 1, ..., N
1. The range of possible sums, R is bounded by an efficiently computable
   min_sum and max_sum.
The lookup table is thus of dimension N x R. For each subset i = 1, ..., N,
we determine the range of values attainable with that subset, which are
simply all the targets of subset i - 1, plus nums[i] (included), and plus 0
(not included). Thus, we perform only R operation per N subsets.
"""

def subset_sum(nums, T):

    # Determine range of possible sums (including 0)
    min_sum, max_sum = 0, 0

    for num in nums:
        if num < 0: min_sum += num
        else: max_sum += num

    # Initialise lookup table
    N, R = len(nums), max_sum - min_sum

    # None represents no path to number
    L = [[None for _ in range(R + 1)] for _ in range(N + 1)]

    # Initialise empty set with target 0 - offset indices by min_sum
    L[0][abs(min_sum)] = []

    # For the first i numbers    
    for i in range(N):
        num = nums[i]

        # Determine all reachable targets
        for j in range(R):
            if not L[i][j] is None:

                # Number not included:
                L[i + 1][j] = L[i][j].copy()
                # Number included:
                L[i + 1][j + num] = L[i][j].copy() + [num]

                # Previous sum j + num = target (offset by min_sum)
                if j + num == T - min_sum:
                    # Check path to target
                    path = L[i + 1][j + num]

                    if not path is None and len(path) > 0:
                        return path # Path to target found

    return None

if __name__ == '__main__':
  print(subset_sum([-1, 2, -3, 4], 0))