Largest differencing method: Difference between revisions

Revision as of 08:40, 12 July 2022

Revision as of 18:48, 19 July 2022

Line 15:

* Proceed in this way until a single number remains. This single number is the difference in sums between the two subsets.

For example, if S = {8,7,6,5,4}, then the resulting difference-sets are 6,5,4,1, after taking out the largest two numbers and inserting the difference back; then 4,1,1, then 3,1 then 2.

Step 3 constructs the subsets in the partition by backtracking. The last step corresponds to {2},{}. Then 2 is replaced by 3 in one set and 1 in the other set: {3},{1}, then {4},{1,1}, then {4,5}, {1,6}, then {4,7,5}, {8,6}, where the sum-difference is indeed 2.