Balanced Partition

January 8, 2024

medium

Problem #

You are given an array nums of integers. Write a function to determine if the array can be partitioned into two subsets such that the sum of elements in both subsets is the same.

Example: #

Input: nums = [1, 5, 11, 5] Output: True Explanation: The array can be partitioned as [1, 5, 5] and [11].

Solution #

The problem is a variation of the “Subset Sum” problem, which is a classic dynamic programming issue. The idea is to determine if there is a subset whose sum is equal to half of the total sum of the array. If such a subset exists, it implies the array can be divided into two subsets with equal sums.

Algorithm Steps: #

Calculate the total sum of the array. If the sum is odd, return False because the array cannot be partitioned into two equal subsets.
Use dynamic programming to find if there’s a subset with a sum equal to half of the total sum.
Create a boolean 2D array dp with dimensions [n+1][sum/2 + 1] where n is the number of elements in nums.
Initialize the first column of dp as True (since a sum of 0 is always possible).
Fill the dp array according to the subset sum problem solution.
Return dp[n][sum/2].

Code in Python: #

def canPartition(nums):
    total_sum = sum(nums)
    if total_sum % 2 != 0:
        return False
    
    subset_sum = total_sum // 2
    n = len(nums)
    dp = [[False for _ in range(subset_sum + 1)] for _ in range(n + 1)]

    for i in range(n + 1):
        dp[i][0] = True

    for i in range(1, n + 1):
        for j in range(1, subset_sum + 1):
            if j < nums[i - 1]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]

    return dp[n][subset_sum]

# Example Usage
print(canPartition([1, 5, 11, 5]))  # Output: True

Code Analysis #

The provided Python code is a solution for the “Balanced Partition” problem, which determines whether an array can be partitioned into two subsets with equal sums. Let’s go through the code step by step:

Function Definition:
```
def canPartition(nums):
```
This defines a function named canPartition that takes an array nums as input.
Calculate Total Sum and Initial Check:
```
total_sum = sum(nums)
if total_sum % 2 != 0:
    return False
```
The total sum of all elements in nums is calculated. If this sum is odd (total_sum % 2 != 0), it’s impossible to split the array into two equal-sum subsets, so the function immediately returns False.
Prepare for Dynamic Programming:
```
subset_sum = total_sum // 2
n = len(nums)
dp = [[False for _ in range(subset_sum + 1)] for _ in range(n + 1)]
```
The target subset sum (subset_sum) is half of the total sum. The dp array is a 2D list of size (n+1) x (subset_sum+1) initialized to False. Each element dp[i][j] will indicate whether there is a subset among the first i numbers of nums that sums up to j.
Initialize First Column of DP Array:
```
for i in range(n + 1):
    dp[i][0] = True
```
This initializes the first column of the dp array to True. This is because a subset sum of 0 is always possible (by selecting no elements).
Fill the DP Table:
```
for i in range(1, n + 1):
    for j in range(1, subset_sum + 1):
        if j < nums[i - 1]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]
```
This nested loop fills up the dp table. For each element nums[i-1] (considering 1-based indexing for clarity), and for each possible sum j:
- If j (the target sum) is less than nums[i-1], we can’t include this element, so we inherit the value from dp[i-1][j].
- Otherwise, we check if we can form the sum either by excluding (dp[i-1][j]) or including (dp[i-1][j - nums[i - 1]]) the current element.
Return the Result:
```
return dp[n][subset_sum]
```
Finally, the function returns the value of dp[n][subset_sum], which indicates whether it’s possible to achieve a subset sum of subset_sum using all elements of nums.

Overall, the code uses a dynamic programming approach to efficiently solve a problem that might seem daunting if tackled with brute force methods. By breaking the problem into smaller subproblems and storing intermediate results, it achieves polynomial time complexity.

Time Complexity: #

O(n * sum/2), where n is the number of elements in nums and sum is the total sum of the array. This is due to the nested loop in the dynamic programming solution.

Space Complexity: #

O(n * sum/2), for the 2D dp array.

This problem is an excellent example of applying dynamic programming to partition problems, balancing computational efficiency with a straightforward approach.