0

Question : If somehow I partition a number array into two sets and their difference in sum is $1$ . Can confirm that the minimum possible difference in sums that can be attained by partitioning the array optimally into two sets is actually $1$?

(say that any element in the array is less than or equal to the max_element of array and greater than $zero$)

example : $3,8,6,4,1,5,7,9$ can be partitioned into $3,8,6,4$ and $1,5,7,9$ with sum difference 1.

(sorry if my example itself is wrong,but I hope my question is clear)

I'm working on a code which divides the array into two sets with minimum sum difference and I want to stop the execution if I get a min difference as $1$ at some point of time.

Sathyaram
  • 173
  • have you seen https://math.stackexchange.com/questions/30690/balanced-2-partition-with-equal-cardinality-cardinality-difference-1-max?rq=1 – Yimin Jan 07 '18 at 07:03
  • @Yimin so from that I can tell that we can actually tell if its 1 or not?That question seemed more likely as a constrained partition though with restrictions put on whether N is even or odd. – Sathyaram Jan 07 '18 at 07:15
  • 1
    If I understand correctly, you said you have already a partition with difference of sums is 1, and you want to confirm the difference is minimal? The answer is yes. – Yimin Jan 07 '18 at 07:19

0 Answers0