Editorial for Subset of Sum S


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.
by: donchominkov

Solutions

  1. O(n * S) solution in Python
def solve(numbers, s):
    sums = [0] * (s + 1)
    sums[0] = True

    for number in numbers:
        for current_sum in range(s, -1, -1):
            if not sums[current_sum]:
                continue

            new_sum = current_sum + number
            if new_sum > s:
                continue

            sums[new_sum] = True
    return sums[s]

Comments

There are no comments at the moment.