#2035

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Partition Array Into Two Arrays to Minimize Sum Difference

Partition an integer array into two equal halves to minimize the absolute difference of their sums using dynamic programming.

array two pointers binary search dynamic programming bit manipulation

Problem Statement

Given an integer array nums containing 2 * n elements, partition it into two arrays of length n such that each element belongs to exactly one array. Your goal is to minimize the absolute difference between the sums of these two arrays, returning this minimum difference.

For example, with nums = [3,9,7,3], one valid partition is [3,9] and [7,3], giving an absolute sum difference of 2. Constraints include 1 <= n <= 15 and elements ranging from -10^7 to 10^7.

Examples

Example 1

Input: nums = [3,9,7,3]

Output: 2

One optimal partition is: [3,9] and [7,3]. The absolute difference between the sums of the arrays is abs((3 + 9) - (7 + 3)) = 2.

Example 2

Input: nums = [-36,36]

Output: 72

One optimal partition is: [-36] and [36]. The absolute difference between the sums of the arrays is abs((-36) - (36)) = 72.

Example 3

Input: nums = [2,-1,0,4,-2,-9]

Output: 0

One optimal partition is: [2,4,-9] and [-1,0,-2]. The absolute difference between the sums of the arrays is abs((2 + 4 + -9) - (-1 + 0 + -2)) = 0.

Constraints

1 <= n <= 15
nums.length == 2 * n
-107 <= nums[i] <= 107

Solution Approach

Split Array and Use Bitmask DP

Divide nums into two halves and generate all possible subset sums for each half using bitmasking. This allows tracking sums efficiently and prepares for merging the halves while targeting sum(nums)/2.

Combine Sums with Binary Search

Sort the subset sums of one half and for each sum in the other half, use binary search to find the closest complementary sum. This reduces the absolute difference calculation to O(log N) per candidate, leveraging ordered arrays.

Compute Minimum Absolute Difference

Iterate over all subset sum combinations and maintain the minimal absolute difference. Return this value, ensuring correctness by checking edge cases where negative numbers could invert the sums.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on generating all subset sums, which is O(2^n) per half, and combining with binary search gives O(2^n log(2^n)). Space complexity is O(2^n) for storing sums of each half.

What Interviewers Usually Probe

Look for efficient handling of subset sums beyond brute-force partitioning.
Expect discussion of state transition dynamic programming and sum targeting.
Watch for correct edge case handling with negative integers.

Common Pitfalls or Variants

Common pitfalls

Assuming a simple greedy split works; it fails with negative numbers.
Not properly generating all subset sums with bitmasking, missing optimal partitions.
Mishandling binary search rounding or bounds when combining halves.

Follow-up variants

Partition into k arrays instead of 2 while minimizing max-min sum difference.
Limit subset sums to positive integers only to simplify DP states.
Allow array length n up to 20, requiring pruning or meet-in-the-middle optimizations.

FAQ

What pattern does Partition Array Into Two Arrays to Minimize Sum Difference follow?

It follows a state transition dynamic programming pattern, often solved with subset sum bitmasking and binary search for optimal combination.

How do I handle negative numbers in this partitioning problem?

Include negative numbers in your subset sum generation and do not rely on greedy heuristics, as they can invert the sums and affect minimal difference.

Is there a faster approach than generating all subsets?

Meet-in-the-middle using halves with binary search on sorted subset sums provides a feasible O(2^n log 2^n) solution for n <= 15.

What is the significance of targeting sum(nums)/2?

Targeting sum(nums)/2 balances the two partitions, minimizing the absolute difference between their sums efficiently.

Can I use standard DP without splitting the array?

For arrays up to 30 elements, splitting into halves with subset sums is more efficient; standard DP on full array can be too large in memory.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

class Solution:
    def minimumDifference(self, nums: List[int]) -> int:
        n = len(nums) >> 1
        f = defaultdict(set)
        g = defaultdict(set)
        for i in range(1 << n):
            s = cnt = 0
            s1 = cnt1 = 0
            for j in range(n):
                if (i & (1 << j)) != 0:
                    s += nums[j]
                    cnt += 1
                    s1 += nums[n + j]
                    cnt1 += 1
                else:
                    s -= nums[j]
                    s1 -= nums[n + j]
            f[cnt].add(s)
            g[cnt1].add(s1)

        ans = inf
        for i in range(n + 1):
            fi, gi = sorted(list(f[i])), sorted(list(g[n - i]))
            # min(abs(f[i] + g[n - i]))
            for a in fi:
                left, right = 0, len(gi) - 1
                b = -a
                while left < right:
                    mid = (left + right) >> 1
                    if gi[mid] >= b:
                        right = mid
                    else:
                        left = mid + 1
                ans = min(ans, abs(a + gi[left]))
                if left > 0:
                    ans = min(ans, abs(a + gi[left - 1]))
        return ans

Continue Practicing

#1755 closest subsequence sum #1994 the number of good subsets #1799 maximize score after n operations