Balanced Partitioning of Array

Balanced Partitioning of Array

February 22, 2024
medium
dynamic programming

Question #

Given an integer array nums of n elements, partition it into two non-empty subsets, S1 and S2, such that the absolute difference between the sum of elements in S1 and the sum of elements in S2 is minimized. Return the minimum absolute difference.

Example #

Input: nums = [1, 2, 3, 4]
Output: 0
Explanation: Partitioning the array into subsets [1, 4] and [2, 3] gives two subsets with equal sums of 5, so the minimum absolute difference is 0.

Input: nums = [1, 1, 3]
Output: 1
Explanation: Partitioning the array into subsets [1, 3] and [1] gives sums of 4 and 1 respectively, so the minimum absolute difference is 1.

Solution Approach #

This problem can be solved using Dynamic Programming, specifically a variation of the 0/1 Knapsack problem. The idea is to find a subset of nums whose sum is as close as possible to half of the total sum of all elements in nums. The problem then reduces to finding the subset with the sum closest to this target.

Algorithm Steps #

  1. Calculate the total sum of the array, totalSum.
  2. Initialize a boolean DP array dp of size totalSum / 2 + 1. dp[i] will be true if there is a subset with sum i, otherwise false.
  3. Set dp[0] to true because a sum of 0 is always possible (with an empty subset).
  4. Iterate through the elements of nums, and for each element num, iterate through the DP array from totalSum / 2 down to num, setting dp[j] = dp[j] || dp[j - num].
  5. After filling the DP array, the largest j for which dp[j] is true represents the largest sum less than or equal to totalSum / 2 that can be achieved by any subset. The minimum absolute difference is then totalSum - 2 * j.

Code # 

def findMinDifference(nums):
    totalSum = sum(nums)
    target = totalSum // 2
    
    dp = [False] * (target + 1)
    dp[0] = True
    
    for num in nums:
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]
    
    for j in range(target, -1, -1):
        if dp[j]:
            return totalSum - 2 * j

# Example usage
print(findMinDifference([1, 2, 3, 4]))  # Output: 0
print(findMinDifference([1, 1, 3]))     # Output: 1

Time Complexity #

The time complexity is O(n * totalSum / 2), where n is the number of elements in nums, because the algorithm iterates through each element and for each element, it potentially iterates through totalSum / 2 possible subset sums.

Space Complexity #

The space complexity is O(totalSum / 2) due to the DP array used to store subset sums up to totalSum / 2.