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:
So, the minimum difference becomes .
Constraints:
-
nums.length
-
nums[i]
Examples
Level up your interview prep. Join Educative to access 80+ hands-on prep courses.