Subset Sum Problem - Medium

Problem : Given a set of integers A, find out if there is a subset of A which add up to a particular integer K.

Formally called the Subset Sum Problem, we are given an NP-Complete problem. To solve this, we have to exhaustively search every subset and verify if they add up to an integer K.

Let's begin with a Brute force DFS search, we're going to construct subsets incrementally until the sum exceeds K. The elements are assumed sorted in the increasing order.

	def subset_sum(lst,K):
	lst.sort()
	sz = len(lst)
	def subset_sum_helper(index,s):
	if index == sz or s >= K : return s == K
	return subset_sum_helper(index + 1, s) or subset_sum_helper(index + 1, s + lst[index])
	return subset_sum_helper(0 , 0 )

view raw Subset Sum DFS hosted with ❤ by GitHub

So we perform a DFS trying to perform every combination of the elements in the set. The recursive function either will include an element in the sum or exclude it. The guard prunes off DFS paths that exceed the sum required.

There is an efficient method for this, using Dynamic Programming. Essentially, we start with a single element, add the next element together to get the new sums possible. These new sums will be the input for the next iteration. I'll explain with an example, say we have {a,b,c}

• You start with a set, lets call it partial_sums = {0}. For each element in the partial_sums we add a to the set. So after one iteration we have {0,0+a} ie {0,a}
• Now for b, repeat the procedure. This gives us partial_sums =  {0,a,b,a+b}
• Finally, c gives us {0,a,b,c,a+c,b+c,a+b+c}
• Note : if any sum exceeds K we don't need to add it to the set (assuming the initial set was sorted, since the sum can only increase.)

Here's the solution implemented.

	def subset_sum_dp(lst,K):
	ways = {0}
	lst.sort()
	for v in lst:
	t = set()
	for w in ways:
	nv = v+w
	if nv == K : return True
	if nv < K:
	t.add(v+w)
	ways.update(t)
	return False

view raw Subset Sum DP hosted with ❤ by GitHub

Here's the complete gist