The Subset Sum (Main72) problem, officially published in SPOJ, is about computing the sum of all integers that can be obtained from the summations over any subset of the given set (of integers). A naïve solution would be to derive all the subsets of the given set, which unfortunately would result in time complexity, given that
is the number of elements in the set.
This post outlines a more efficient (pseudo-polynomial) solution to this problem using Dynamic Programming and F#. Additionally, we post C# code of the solution.
Note that we have solved a similar problem in Party Schedule (PARTY) with F# blog-post.
Interpretation¶
This problem provides a set of integers , and specifies the following constraints–
The size of the given set, i.e., 
Given this input, we would like to find all the integers: and
is the sum of the items of any subset over
. Afterward, we sum all these integers, and return it as the result to the problem instance.
In essence, we reduce this problem as follows: Given , can we express it using any subset over
? If yes, we include it in the solution set for summation. Interestingly, we realize that the stated problem is a special case of a more general problem called Subset Sum, given that the sum is
.
Algorithm¶
What would be the maximum possible value for ? Indeed,
is not practical at all, as
can be bounded by the following upper limit:
, i.e., the summation of all the items in
. This observation effectively reduces the search space to
, for a given
.
It implies that a naïve algorithm would require to iterate all the subsets over and verify whether their sum is within
. Recall that, due to its exponential time complexity, it is quite impractical .
Using dynamic programming technique, a pseudo-polynomial algorithm can be derived, as the problem has an inherent optimal substructure property. That is, a solution of an instance of the problem can be expressed as the solutions of its subproblems, as described next.
We define as the function that determines whether the summation over any subset
can result in the integer
. So, it yields
if sum
can be derived over any subset
, otherwise,
. Also, note that,
and
.
To define the recurrence, we describe in terms of its smaller subproblems as follows.
In Eq. (1), the first case refers to the fact that is larger than
. Consequently,
can not be included in the subset to derive
. Then, the case 2 of Eq. (1) expresses the problem
into two subproblems as follows: we can either ignore
though
, or we can include it. Using any case stated in Eq. (1), if we can derive
i.e.
= true, we can include it in the solution set.
As we can see overlapping subproblems, we realize that we can effectively solve them using a bottom-up dynamic programming approach. What about the base cases?
Using a table– dp, we can implement the stated algorithm as follows.
| let computeSubsetSum (set:int array, n:int, sum:int):int = | |
| // dp[i,j] = True, if subset of [0..i-1] sum | |
| // equals to : | |
| // j-set[i] => ith item is included | |
| // or | |
| // j => ith item is not included | |
| let dp:bool[,] = Array2D.zeroCreate (n+1) (sum+1) | |
| // This dp tries answer folloowing question, given a sum | |
| // j, whether we can derive it by summing any subset of | |
| // [0..i]. It computes this answer in bottom up manner, | |
| // hence, if starting from (i,j) if it can reach (i,0), the | |
| // answer is yes. Otherwise, if sum<>0 but i=0, then answer is | |
| // no due to the fact that, using any subsets, the sum cannot be | |
| // computed. | |
| // Therefore. | |
| // base case 1 : given sum = 0, answer is true | |
| // sum is zero with the provided set of items. | |
| // Hence, storing it as 0 | |
| for i = 0 to n do | |
| dp.[i,0] <- true | |
| // base case 2 : sum <> 0 but OPT = empty --> | |
| // answer is false | |
| for j=1 to sum do | |
| dp.[0,j] <- false | |
| for i = 1 to n do | |
| let v_i = set.[i-1] | |
| for j = 1 to sum do | |
| dp.[i,j] <- | |
| if j - v_i < 0 then | |
| // we can't include i th item in OPT | |
| dp.[i-1,j] | |
| else | |
| dp.[i-1,j]||dp.[i-1,j-v_i] | |
| let mutable result = 0 | |
| for j=1 to sum do | |
| result <- result+ | |
| ( if dp.[n,j] = true then | |
| j | |
| else | |
| 0 | |
| ) | |
| result |
In essence, the Nth row in the table provides the set of integers that can be derived by summing over any subset . Thereby, we compute the summation of all these integers that satisfies subsum(N,j) = true, and returns it as the result.
Conclusion¶
Full source code of the solution can be downloaded from this gist. For C# source code, please visit following gist. Please leave a comment if you have any question/suggestion regarding this post.
Enough said… now, it’s time for a 
and a new problem. See you soon; till then, happy problem-solving!
See Also
SPOJ 97. Party Schedule (PARTY) with F#.
UVa 10664. Luggage.
as D, which can be defined using a 
and 
are empty strings, denoted as 
:
, where 
is the last character of 
contains rest of the characters. Same goes for 
. We define edit distance between 
.
can be defined as the minimum, or the least expensive one of the following three alternatives stated in the above equation.
, then the overall distance is simply 
. Otherwise, we need a substitution operation that replaces 
with 
adilakhter λ 