Sum of two subsets as close as possible

Mike found a long tape in his home. He proceeded to write some sequence of integers. Now he'd like to cut the tape in such a place that the difference between the sum of the integers on one part and on the other is as close to zero as possible (on one part there has to be at least one number). You're to print the absolute value of this difference.

Input: n (2 ≤ n ≤ 10⁶) meaning the amount of numbers written on the tape and then n integers a_i (-10³ ≤ a₁ ≤ 10³) as the numbers written on the tape.

Output: One integer being a minimal absolute value of difference between the two pa开发者_开发百科rts.

Example:

6

1 2 3 4 5 6

Should output:

1

I have a feeling I've read a problem like this somewhere before.. I don't know how to solve it, though. I mean, I have a clue but I don't know if it's right. Should I compute the sum of the whole tape first and then compute from left to right till I'm as close to the part being a half of the whole tape as possible? I mean: I sum the numbers from left to right constantly checking if I've exceeded the half of the whole set. If a sum of the subset is equal to the half - we print zero. If the exact half is not possible, we check the closest below and above and output the closest one. Is that OK?

Start at one end of the tape and calculate the sum. Write down the sub-sum (sum up to that number) as you are going along. Now the problem is a simple search problem where we can search the sub-sums for the one closest to the total sum divided by two using for instance binary search.

Yes this is exactly how you would go about it. You can keep track of the sum of the left partition and the right partition by first summing the array and then subtracting each element from the right sum and adding it to the left sum.

auto right_sum = accumulate(tape.begin(),tape.end(),0); // sum all the elements
decltype(right_sum) left_sum = 0;
decltype(right_sum) smallest_difference = abs(right_sum-left_sum);
auto best_partition = tape.begin();
for (auto it=tape.begin();it!=tape.end();++it) {
  left_sum += *it;
  right_sum -= *it;
  if (abs(right_sum-left_sum)<smallest_difference) {
    smallest_difference = abs(right_sum-left_sum);
    best_partition = it;
  } 
}