Reputation: 173
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
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