Dynamic Programming in 5 easy steps  Examples  Set partitioning
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.The 5 easy steps are:
If there is a set S with n elements, then if we assume S1 has m elements, S2 must have nm elements and the value of abs(sum(S1) – sum(S2)) should be minimum.
 define subproblems, count number of subproblems
 guess (part of solution), count number of choices
 relate subproblem solutions, compute time per subproblem
 recurse + memoize OR build DP table bottomup check subproblems acyclic/topological order, time = time per subproblem · number of subproblems
 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 totalSumchosenSetSum.
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) = totalSumX, because that’s the end of partitioning.
The time complexity of this approach is:
1 

Yey, we have pseudopolynomial 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).
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
1 

Memoization added
1 

Full solution with parent pointers and examples
1 
