Last time we have covered Text Justification problem, this time we will do something harder. Solution in 5 easy steps!

The problem statement is as follows:

Given a set S of positive integers, divide it into two sets S1 and S2 such that the absolute difference between their sums is minimum.

If there is a set S with n elements, then if we assume S1 has m elements, S2 must have n-m elements and the value of abs(sum(S1) – sum(S2)) should be minimum.
The 5 easy steps are:
1. define subproblems, count number of subproblems
2. guess (part of solution), count number of choices
3. relate subproblem solutions, compute time per subproblem
4. recurse + memoize OR build DP table bottom-up check subproblems acyclic/topological order, time = time per subproblem · number of subproblems
5. solve original problem: = a subproblem OR by combining subproblem solutions ⇒ extra time
Taking an example, assume a set S={ 1, 6, 11, 5}.
Step 1. As previously, we want to divide the problem to subproblems.
How this can be done? Suffixes, prefixes or the mix of those two are usually the answer. It’s natural to imagine that in the middle of processing the set looks at some point as follows .., 11, 5. At this very point we already assumed we are working on suffixes.
In that situation we can either include the 11 in the set S1 or in the set S2. I’ll say that we take or leave the number, because we have only two choices.
Related, very important aspect - we have to track only one sum! The other one is just totalSum-chosenSetSum.
Getting back to our situation, what is the “context” of the subproblem? Does it matter how we got to this point? Not at all, what matters is only the chosenSetSum. Obviously, we have to also keep track of our current item index. Here we have it, the subproblems.

Step 2. How our guess will look like? We can increase the sum and progress with the problem,
or we can just progress with the problem, assuming we leave the item and it will be in the second set.

Step 3. Now we have to glue two pieces togeter. Our DP function will have two arguments as noted above, chosenSetSum and index.
We want to optimize for the minimum difference between the sets and that’s what will be returned by the DP function. All in all, the equation is as follows:
DP(chosenSetSum, i) = min from:
• DP(chosenSetSum, i+1) //when skipping the i’th item
• DP(chosenSetSum + inputSet[i], i+1)) //when taking the i’th item
The corner case is DP(X, inputSet.Length) = totalSum-X, because that’s the end of partitioning.
The time complexity of this approach is:
Yey, we have pseudo-polynomial time solution.

Step 4. Is it actually an acyclic graph of DP function invocations? My reasoning here is that we have two dimensions (chosenSetSum and item index) where both increase and there is an end when the second variable reaches input set cardinality, thus it’s finite algorithm.

Step 5. We start with chosenSetSum=0 and at the first index, therefore our solution is at DP(0,0).

## The Code

Having the 5 steps figured out, it’s relatively easy to code the solution.

### Pure DP algorithm coded without memorization

How cool is that? 6 lines of code for almost working solution!