...

/

Partition Array Into Two Arrays to Minimize Sum Difference

Partition Array Into Two Arrays to Minimize Sum Difference

Let's solve the Partition Array Into Two Arrays to Minimize Sum Difference problem using Dynamic Programming.

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

Access this course and 1400+ top-rated courses and projects.