Partition Array Into Two Arrays to Minimize Sum Difference

Statement

Suppose you are given an array, nums, containing positive numbers. You need to partition the array into two arrays such that the absolute difference between their sums is minimized.

Note: Each element of the nums array should be present in one of the partitioned arrays.

Let’s say you have the following array:

  • [2, 3, 1]

The two partitioned arrays with the minimum difference in their sums are:

  • [2,1],sum=3[2, 1], sum = 3
  • [3],sum=3[3], sum = 3

So, the minimum difference becomes 33=0|3-3| = 0.

Constraints:

  • 11\leq nums.length 900\leq 900
  • 11\leq nums[i] 104\leq 10^4

Examples

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.