hard Partition Array Into Two Arrays to Minimize Sum Difference

Problem Statement

You are given an integer array nums that contains 2 * n elements. Split nums into two separate arrays, each of length n, in such a way that the absolute difference between the sums of elements of these two arrays is minimized. To partition nums, put each element of nums into one of the two arrays.

Return this minimum possible absolute difference.

Examples

Example 1:

• Input: nums = [1, 6, 11, 5]
• Output: 1
• Explanation: The array can be partitioned as [1, 6] and [11, 5]. The sum of the first array is 7, and the sum of the second array is 16. The absolute difference between these sums is |7 - 16| = 9. However, if we partition the array as [1, 11] and [6, 5], the sums become 12 and 11, respectively, and the absolute difference becomes |12 - 11| = 1, which is the minimum possible difference.

Example 2:

• Input: nums = [2, 3, 9, 12]
• Output: 2
• Explanation: We can partition the array into [2, 12] and [3, 9], resulting in sums of 14 and 12. The absolute difference between these sums is |14 - 12| = 2.

Example 3:

• Input: nums = [7, 4, 5, 9]
• Output: 1
• Explanation: The array can be split into [7, 5] and [4, 9], resulting in sums of 12 and 13. The absolute difference is |12 - 13| = 1, which is the minimum possible difference for this input.

Constraints:

• 1 <= n <= 15
• nums.length == 2 * n
• -10⁷ <= nums[i] <= 10⁷

Solution

To solve this problem, we generate all possible subsets of the given array and calculate their sums. By splitting the array into two halves, we can explore all possible subset sums for each half separately. For each subset size in the first half, we aim to find the closest possible subset sum in the second half that balances the sums between the two halves. We use binary search to efficiently find the closest subset sums in the second half. The goal is to minimize the absolute difference between the total sum and twice the sum of the selected subsets, as this difference gives us the minimum partition difference.

This approach is efficient because it leverages the "meet in the middle" technique, reducing the problem's complexity by focusing on subset sums from two halves instead of generating and comparing all possible subset sums of the entire array. Sorting the subset sums of the second half allows us to use binary search, ensuring that the closest possible sum is found quickly, thus optimizing the solution.

Step-by-Step Algorithm

1. Initialize Variables:

   • Step 1: Initialize totalSum to 0 and iterate through the array nums to calculate the total sum. This sum is needed to determine the difference between the sums of the two partitions.
   • Step 2: Initialize minimumDifference to a large value (Integer.MAX_VALUE) to track the smallest difference found.

2. Generate Subset Sums for Each Half:

   • Step 3: Divide nums into two halves: the first half (left) and the second half (right).
   • Step 4: For each half, generate all possible subset sums using the generateSubsetSums function. This function:
     • Creates an array of lists, subsetSums, where each list stores sums corresponding to subsets of a particular size.
     • For example, subsetSums[0] stores sums of subsets with 0 elements, subsetSums[1] stores sums of subsets with 1 element, and so on. The use of nested arrays (or lists) allows the algorithm to categorize subset sums based on the number of elements in each subset.

3. Sort the Subset Sums of the Second Half:

   • Step 5: Sort each list in rightSubsetSums (the second half) to allow efficient searching. Sorting is essential because it enables the use of binary search to quickly find the closest sums in the next steps.

4. Compare Subset Sums to Find Minimum Difference:

   • Step 6: Iterate through each subset size in leftSubsetSums.

     • Step 6.1: For each subset sum in leftSubsetSums, calculate the targetSum needed from the second half to balance the sums between the two partitions. This target is calculated as totalSum / 2 - leftSum.

     • Step 6.2: Calculate remainingElements = n / 2 - i to ensure we are comparing sums of subsets that together have n/2 elements.

     • Step 6.3: Use binary search on rightSubsetSums[remainingElements] to find the closest sum to targetSum. If binary search returns a negative index (meaning the exact target wasn't found), adjust the index to the insertion point by computing index = -(index + 1).

     • Step 6.4: If index is within bounds (index < rightSubsetSums[remainingElements].size()), calculate the difference between the total sum and twice the sum of the subsets (leftSum + rightSubsetSums[remainingElements].get(index)):

       • The goal is to minimize the absolute difference between the sums of the two partitions, which is why we subtract twice the sum of the selected subsets from totalSum.
       • Update minimumDifference if this difference is smaller than the previously found differences.

     • Step 6.5: If index > 0, check the sum at the previous index (index - 1). This step is crucial because binary search might land on an index that isn't the closest to the target sum. The previous index might provide a smaller difference:

       • Checking the previous index ensures that we consider both the closest larger and smaller sums, which is essential for minimizing the difference.
       • Update minimumDifference if it results in a smaller difference.

5. Return the Result:

   • Step 7: After iterating through all possible subset sums and updating minimumDifference, return the smallest difference found.

Algorithm Walkthrough

• Input: [1, 6, 11, 5]
• Step 1: Calculate totalSum = 1 + 6 + 11 + 5 = 23.
• Step 2: Initialize minimumDifference = Integer.MAX_VALUE.

Generate Subset Sums:

• Left half: [1, 6]
  • For mask = 0: Sum = 0, Subset size = 0 → leftSubsetSums[0] = [0].
  • For mask = 1: Sum = 1, Subset size = 1 → leftSubsetSums[1] = [1].
  • For mask = 2: Sum = 6, Subset size = 1 → leftSubsetSums[1] = [1, 6].
  • For mask = 3: Sum = 7, Subset size = 2 → leftSubsetSums[2] = [7].
• Right half: [11, 5]
  • For mask = 0: Sum = 0, Subset size = 0 → rightSubsetSums[0] = [0].
  • For mask = 1: Sum = 11, Subset size = 1 → rightSubsetSums[1] = [11].
  • For mask = 2: Sum = 5, Subset size = 1 → rightSubsetSums[1] = [11, 5].
  • For mask = 3: Sum = 16, Subset size = 2 → rightSubsetSums[2] = [16].
• Sort rightSubsetSums:
  • rightSubsetSums[1] becomes [5, 11].

Compare Subset Sums:

• Iteration 1: (i = 0, leftSubsetSums[0] = [0])

  • leftSum = 0
    • remainingElements = 2 - 0 = 2
    • targetSum = 11.5 - 0 = 11.5
    • Binary search in rightSubsetSums[2] ([16]):
      • Closest sum = 16.
      • Difference = |23 - 2 * (0 + 16)| = |23 - 32| = 9.
      • Update minimumDifference = 9.

• Iteration 2: (i = 1, leftSubsetSums[1] = [1, 6])

  • leftSum = 1
    • remainingElements = 1
    • targetSum = 11.5 - 1 = 10.5
    • Binary search in rightSubsetSums[1] ([5, 11]):
      • Closest sum = 11.
      • Difference = |23 - 2 * (1 + 11)| = |23 - 24| = 1.
      • Update minimumDifference = 1.
  • leftSum = 6
    • remainingElements = 1
    • targetSum = 11.5 - 6 = 5.5
    • Binary search in rightSubsetSums[1] ([5, 11]):
      • Closest sum = 5.
      • Difference = |23 - 2 * (6 + 5)| = |23 - 22| = 1.
      • minimumDifference remains 1.

• Iteration 3: (i = 2, leftSubsetSums[2] = [7])

  • leftSum = 7
    • remainingElements = 0
    • targetSum = 11.5 - 7 = 4.5
    • Binary search in rightSubsetSums[0] ([0]):
      • Closest sum = 0.
      • Difference = |23 - 2 * (7 + 0)| = |23 - 14| = 9.
      • minimumDifference remains 1.

Final Result:

• The smallest difference is 1. Thus, the output is 1.

Code

import java.util.*;

public class Solution {
    // Generate all possible subset sums for each subset size
    public List<Integer>[] generateSubsetSums(int[] nums) {
        int length = nums.length; // Length of the array
        List<Integer>[] subsetSums = new ArrayList[length + 1]; // Array of lists for subset sums
        for (int i = 0; i <= length; i++) subsetSums[i] = new ArrayList<>(); // Initialize each list

        // Generate all subsets using bitmask
        for (int mask = 0; mask < (1 << length); mask++) {
            int sum = 0;
            int subsetSize = 0, index = 0;
            int bitmask = mask;
            
            // Calculate the sum of the current subset
            while (bitmask != 0) {
                if ((bitmask & 1) == 1) {
                    sum += nums[index];
                    subsetSize++;
                }
                index++;
                bitmask >>>= 1; // Shift right to process next bit
            }
            // Add the subset sum to the list for its size
            subsetSums[subsetSize].add(sum);
        }
        return subsetSums;
    }

    // Compute the minimum difference between two subsets
    public int minimumDifference(int[] nums) {
        int n = nums.length;
        int minimumDifference = Integer.MAX_VALUE; // Start with a large value
        int totalSum = 0;

        // Calculate total sum of the array
        for (int num : nums) totalSum += num;

        // Generate subset sums for each half of the array
        List<Integer>[] leftSubsetSums = generateSubsetSums(Arrays.copyOfRange(nums, 0, n / 2));
        List<Integer>[] rightSubsetSums = generateSubsetSums(Arrays.copyOfRange(nums, n / 2, n));

        // Sort sums of the second half for efficient searching
        for (int i = 0; i < rightSubsetSums.length; i++) Collections.sort(rightSubsetSums[i]);

        // Compare subset sums from both halves to find the minimum difference
        for (int i = 0; i < leftSubsetSums.length; i++) {
            for (Integer leftSum : leftSubsetSums[i]) {
                int remainingElements = n / 2 - i; // Number of elements left in the second half
                int targetSum = totalSum / 2 - leftSum; // Target sum to find in the second half

                // Find the closest sum in the second half using binary search
                int index = Collections.binarySearch(rightSubsetSums[remainingElements], targetSum);
                index = index < 0 ? -(index + 1) : index; // Adjust index for insertion point

                // Check the closest sums and update the minimum difference
                if (index < rightSubsetSums[remainingElements].size()) {
                    // Compute the difference using the closest sum at the found index
                    minimumDifference = Math.min(minimumDifference, 
                        Math.abs(totalSum - 2 * leftSum - 2 * rightSubsetSums[remainingElements].get(index)));
                }
                // If the index is greater than 0, check the sum at the previous index
                if (index > 0) {
                    minimumDifference = Math.min(minimumDifference, 
                        Math.abs(totalSum - 2 * leftSum - 2 * rightSubsetSums[remainingElements].get(index - 1)));
                }
            }
        }
        return minimumDifference; // Return the minimum difference found
    }

    // Main method to test the solution
    public static void main(String[] args) {
        Solution solution = new Solution();

        // Test cases
        System.out.println(solution.minimumDifference(new int[]{1, 6, 11, 5})); // Output: 1
        System.out.println(solution.minimumDifference(new int[]{2, 3, 9, 12})); // Output: 2
        System.out.println(solution.minimumDifference(new int[]{7, 4, 5, 9}));  // Output: 1
    }
}

Complexity Analysis

Time Complexity

• The generateSubsetSums function generates all possible subset sums for an array of size n. Since there are 2ⁿ subsets, generating all subset sums takes `O(2ⁿ * n) time.
• The Collections.sort() function sorts the subset sums, which takes O(2ⁿ * log(2ⁿ)) = O(2ⁿ * n) time.
• The binary search for each subset sum from the first half in the second half's sorted subset sums takes O(n * log(2ⁿ)) = O(n²) time for each subset, and there are 2ⁿ such subsets. This results in a time complexity of O(2ⁿ * n²) for this step.
• Overall, the time complexity of the entire solution is O(2ⁿ * n²).

Space Complexity

• The space complexity is mainly due to storing the subset sums, which is O(2ⁿ) for each half of the array. Since we store the subset sums for both halves, the space complexity is O(2ⁿ + 2ⁿ) = O(2ⁿ).