Equal Partition Array — Problem Statement & Solution Guide
Problem Description
Given a non-empty array nums consisting of positive integers, determine whether it is possible to split the array into two disjoint subsets such that the sum of the elements in each subset is identical. The subsets must be non-empty and every element in nums must belong to exactly one of the two subsets.
Return true if such a partition exists; otherwise, return false.
This problem reduces to checking if there exists a subset of nums whose sum is exactly half of the total sum of the array. If the total sum is odd, no such partition is possible.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Equal Partition Array"
WHY DOES IT MATTER?
The Equal Partition pattern exemplifies the broader class of knapsack‑style DP problems where each item can be chosen at most once. Mastery of this pattern unlocks efficient solutions for budgeting, load balancing, and resource allocation tasks that appear across system design interviews.
OPTIMIZATION CHALLENGE
The key insight is to limit the DP state to half of the total sum and to iterate the DP array backwards, which prevents double‑counting an element and reduces space from O(n*sum) to O(sum). This transforms an exponential search into a pseudo‑polynomial one.
REAL-WORLD CONNECTION
Think of a distributed storage system that must split a set of data blocks into two shards with equal total size to achieve balanced I/O; the DP algorithm mirrors the decision process of assigning each block to one of the two shards while keeping the size difference zero.
During an interview, write the 1‑D DP array first, then immediately discuss the reverse iteration trick; this shows you understand both correctness and space optimization, and it often earns extra credit.
COMPLEXITY AT A GLANCE
O(n * total/2)O(total/2)Core Theory — Why This Approach?
The Equal Partition problem is a classic instance of the Subset Sum decision problem, which is known to be NP‑complete. The naive solution enumerates every possible subset, leading to O(2^n) time, which quickly becomes infeasible as n grows beyond 30. The optimal paradigm leverages the fact that we only need to know whether a subset can achieve half of the total sum; this transforms the problem into a bounded knapsack where each number can be used at most once. By using dynamic programming (DP) over the achievable sums up to target = total/2, we can collapse the exponential search space into a pseudo‑polynomial algorithm that runs in O(n * target) time and O(target) space, or even O(target) space with a 1‑dimensional DP array.
Why does this DP work? For each number, we update the reachable sums in reverse order to avoid reusing the same element multiple times. If after processing all numbers the target sum is marked reachable, a valid partition exists. This approach scales to input sizes where the sum of elements is moderate (e.g., up to 10^5), which is typical for interview constraints, while still guaranteeing correctness for all positive integer arrays.
Interview Questions on This Problem
Q1How would you modify the solution if the array could contain zero or negative numbers?
Zeroes can be ignored because they do not affect the sum; negative numbers break the subset‑sum DP assumption of monotonic increase, so you would need to shift the range by adding an offset equal to the absolute sum of negatives and use a DP table that spans the new range, or alternatively convert the problem to a variation of the Partition problem using meet‑in‑the‑middle.
Q2Can you solve the Equal Partition problem in O(n) time using any mathematical property?
Only when additional constraints hold, such as all numbers being powers of two or the total sum being small enough to fit in a bitmask; otherwise, O(n) is impossible because the problem is NP‑complete and requires examining combinations of elements.
Q3Explain how you would adapt the DP solution to also return the actual subsets, not just a boolean answer.
Maintain a predecessor array or back‑pointer for each reachable sum that records which element contributed to reaching that sum; after DP finishes, trace back from the target sum to reconstruct one subset, and the remaining elements form the complementary subset.
Examples
Input
nums = [1, 5, 11, 5]
Output
true
Explanation: The total sum is 1 + 5 + 11 + 5 = 22. Half of the total sum is 11. We need to find a subset that sums to 11. The subset [1, 5, 5] sums to 11, and the remaining subset [11] also sums to 11. Since both subsets have equal sums, the answer is true.
Input
nums = [1, 2, 3, 5]
Output
false
Explanation: The total sum is 1 + 2 + 3 + 5 = 11. Since 11 is odd, it cannot be evenly divided into two equal integer sums. Therefore, no valid partition exists, and the answer is false.
Input
nums = [3, 3, 3, 3, 3]
Output
false
Explanation: The total sum is 3 * 5 = 15. Since 15 is odd, it is impossible to partition the array into two subsets with equal sums. The answer is false.
Input
nums = [2, 2, 2, 2, 2, 2]
Output
true
Explanation: The total sum is 2 * 6 = 12. Half of the total sum is 6. We can form one subset as [2, 2, 2] (sum = 6) and the other as [2, 2, 2] (sum = 6). Both subsets have equal sums, so the answer is true.
Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^4
- The sum of all elements in nums will not exceed 10^5
Optimal Approach & Strategy
Use a 1‑dimensional DP array to record which sums up to target are achievable, updating it in reverse for each element; this runs in O(n * target) time and O(target) space.
Brute Force Approach
Enumerate every possible subset, compute its sum, and check if it equals half of the total sum; this requires O(2^n) time and is impractical for large n.
Verified Code Solutions
function canPartition(nums) {
if (nums.length === 0) return false;
let sum = nums.reduce((a, b) => a + b, 0);
if (sum % 2 !== 0) return false;
sum = Math.floor(sum / 2);
let dp = new Array(nums.length + 1).fill(false).map(() => new Array(sum + 1).fill(false));
dp[0][0] = true;
for (let i = 1; i <= nums.length; i++) {
for (let j = 0; j <= sum; j++) {
if (j < nums[i - 1]) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
}
}
}
return dp[nums.length][sum];
}class Solution {
public:
bool canPartition(vector<int>& nums) {
if (nums.size() == 0) return false;
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 != 0) return false;
sum = sum / 2;
bool dp[nums.size() + 1][sum + 1];
memset(dp, false, sizeof(dp));
dp[0][0] = true;
for (int i = 1; i <= nums.size(); i++) {
for (int j = 0; j <= sum; j++) {
if (j < nums[i - 1]) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
}
}
}
return dp[nums.size()][sum];
}
};public boolean canPartition(int[] nums) {
if (nums.length == 0) return false;
int sum = 0;
for (int num : nums) {
sum += num;
}
if (sum % 2 != 0) return false;
sum = sum / 2;
boolean[][] dp = new boolean[nums.length + 1][sum + 1];
dp[0][0] = true;
for (int i = 1; i <= nums.length; i++) {
for (int j = 0; j <= sum; j++) {
if (j < nums[i - 1]) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
}
}
}
return dp[nums.length][sum];
}def canPartition(nums):
if not nums:
return False
total_sum = sum(nums)
if total_sum % 2 != 0:
return False
target_sum = total_sum // 2
dp = [[False] * (target_sum + 1) for _ in range(len(nums) + 1)]
dp[0][0] = True
for i in range(1, len(nums) + 1):
for j in range(target_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[-1][-1]function canPartition(nums) {
if (nums.length === 0) return false;
let sum = nums.reduce((a, b) => a + b, 0);
if (sum % 2 !== 0) return false;
sum = Math.floor(sum / 2);
let dp = new Array(nums.length + 1).fill(false).map(() => new Array(sum + 1).fill(false));
dp[0][0] = true;
for (let i = 1; i <= nums.length; i++) {
for (let j = 0; j <= sum; j++) {
if (j < nums[i - 1]) {
dp[i][j] = dp[i - 1][j];
} else {
dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
}
}
}
return dp[nums.length][sum];
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.