Largest differencing method: Difference between revisions

Revision as of 18:48, 19 July 2022

Revision as of 18:55, 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 {8,7} and inserting the difference 8-7=1 back; then 4,1,1, then 3,1 then 2.

Repeat the steps and then we have {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.