Balanced Partition
January 8, 2024
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]
wheren
is the number of elements innums
.  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 arraynums
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 equalsum subsets, so the function immediately returnsFalse
. 
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. Thedp
array is a 2D list of size(n+1) x (subset_sum+1)
initialized toFalse
. Each elementdp[i][j]
will indicate whether there is a subset among the firsti
numbers ofnums
that sums up toj
. 
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 toTrue
. This is because a subset sum of0
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 elementnums[i1]
(considering 1based indexing for clarity), and for each possible sumj
: If
j
(the target sum) is less thannums[i1]
, we can’t include this element, so we inherit the value fromdp[i1][j]
.  Otherwise, we check if we can form the sum either by excluding (
dp[i1][j]
) or including (dp[i1][j  nums[i  1]]
) the current element.
 If

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 ofsubset_sum
using all elements ofnums
.
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.