Minimum Maximum Difference
MediumPractice library · +20 XPbinary searchgreedy
Given N integers, partition them into two subsets such that the absolute difference between the sums of the two subsets is minimized. Print this minimum possible absolute difference.
Input
The first line contains an integer N. The second line contains N space-separated integers.
Output
Print a single integer: the minimum absolute difference between the sums of the two subsets.
Constraints
1 <= N <= 40 1 <= a_i <= 1000
Time limit 2 s (native code; slower languages get more)Memory 256 MB14 hidden tests
Example 1
Input
3 1 2 3
Output
0
The numbers are 1, 2, 3. Total sum is 6. The partition {{1,2}, {3}} gives sums 3 and 3, with a difference of 0. This is the minimum possible.
Example 2
Input
4 10 20 30 40
Output
0
The numbers are 10, 20, 30, 40. Total sum is 100. The partition {{10, 40}, {20, 30}} gives sums 50 and 50, with a difference of 0.
Hints
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
Example 1 input
3 1 2 3
Example 2 input
4 10 20 30 40