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
Step 3. Now we have to glue two pieces togeter. Our DP function will have two arguments as noted above, chosenSetSum and index.
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
1 

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
Pure DP algorithm coded without memorization
1 

Memoization added
1 

Full solution with parent pointers and examples
1 
