CODEWITHSUNDEEP
pythonalgorithmmath
Alex_H
Alex_H

Reputation: 173

How to solve subset sum problem with array of size sum+1

Since the problem isn't new and there is a lot of algorithms that solve it I supposed that the question can be duplicating but I didn't find any.

There is a set of an elements. The task is to find is there a subset with the sum equal to some s variable.

Primitive solution is straightforward and can be solved in exponential time. DP recursive approach propose to add memoization to reduce complexity or working with a 2D array (bottom-up).

I found another one in the comment on geeksforgeeks but can't understand how it works.

def is_subset_sum(a, s):
    n = len(a)
    res = [False] * (s + 1)
    res[0] = True
    for j in range(n):
        i = s
        while i >= a[j]:
            res[i] = res[i] or res[i - a[j]]
            i -= 1
    return(res[s])

Could someone please explain the algorithm? What an elements of the array is actually meaning? I'm trying to trace it but can't handle with it.

Upvotes: 1

Views: 282

Answers (1)

גלעד ברקן
גלעד ברקן

Reputation: 23955

Putting words to the code: trying each element in the list in turn, set a temporary variable, i, to the target sum. While i is not smaller than the current element, a[j], the sum equal to the current value of i is either (1) already reachable and marked so, or (2) is reachable by adding the current element, a[j], to the sum equal to subtracting the current element from the current value of i, which we may have already marked. We thus enumerate all the possibilities in O(s * n) time and O(s) space. (i might be a poor choice for that variable name since it's probably most commonly seen representing an index rather than a sum. Although, in this case, the sums we are checking are themselves also indexes.)

Upvotes: 1

Related Questions