# Balanced Partitioning of Array

##### February 22, 2024

### 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 #

- Calculate the total sum of the array,
`totalSum`

. - 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`

. - Set
`dp[0]`

to`true`

because a sum of`0`

is always possible (with an empty subset). - 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]`

. - 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`

.