Problem
Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.
Constraints
1 <= nums.length <= 2001 <= nums[i] <= 100
Example
Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11]
Approach I (Brute Force with Bitmasking)
The brute-force method involves generating all subsets of the array and partitioning the array into included elements and excluded elements. Then we determine whether the sum of the included elements and the sum of the excluded elements are equal.
We use bitmasking to generate all possible subsets. For each subset, we compute both the selected and remaining elements sums and check if both are equal. This is done by iterating over all possible masks (bitmasks) and computing the sums of elements included and excluded by the mask.
Bitmasking is discussed in detail in this post – Bitmasking
This exhaustive approach guarantees correctness by covering all subsets because it evaluates every possible combination of included and excluded elements. However, it is computationally expensive due to the exponential number of subsets ie. 2N in total.
Example
Consider the input: nums = [3, 11, 8]
There are 23 = 8 possible subsets:
{}
{3}
{11}
{8}
{3, 11}
{11, 8}
{3, 8}
{3, 11, 8}
One such valid subset is {11}, whose complement is {3, 8}. The sum of {11} is 11 and the sum of {3, 8} is also 11. Since both subsets are non-empty and have equal sums, the function returns true.
However, in the current bitmask approach, for every subset S, we also check its complement ~S. That means we’re checking both {A}, {B} and {B}, {A}, effectively counting the same partition twice.
We can avoid this by only checking subsets where the mask is less than its complement — or simply by considering only the first half of the bitmask space.
This works because:
- For a set of size
N, every subset has a complement. - If
includedSum == excludedSum, then so does the complement. - So, we only need to check one representative per pair.
This can be done by looping only till 2(N-1).
Pseudocode
CAN-PARTITION-BRUTE(nums[0..N-1])
1. totalSubsets ← 2N-1
2. for mask = 0 to totalSubsets - 1
3. includedSum ← 0
4. excludedSum ← 0
5. for i = 0 to N - 1
6. if mask & (1 << i) // i-th element is included in subset
7. includedSum += nums[i]
8. else
9. excludedSum += nums[i]
10. if includedSum != 0 && includedSum == excludedSum
11. return true
12. return false
Code Implementation
bool canPartition(vector<int>& nums) {
int N = (int) nums.size();
long long totalSubsets = (1LL << (N - 1)); // Avoid duplicate partitions
for (long long mask = 0; mask < totalSubsets; mask++) {
int includedSum = 0, excludedSum = 0;
for (int i = 0; i < N; i++) {
if (mask & (1LL << i)) {
includedSum += nums[i];
} else {
excludedSum += nums[i];
}
}
if (includedSum != 0 && includedSum == excludedSum) {
return true;
}
}
return false;
}
Time Complexity
We generate every subset using bitmasking. For each subset, we check if the sums of both partitions are equal, resulting in a time complexity of O(2N * N) or O(2N-1 * N) with optimization, which becomes impractical for larger values of N.
Space Complexity
O(1) — No extra space is used except for variables.
Note: We can safely ignore the case where either the included or excluded subset is empty. The problem statement doesn’t mention handling empty subsets, and given the problem constraints, a subset with a sum of 0 isn’t possible.
Approach II (Dynamic Programming)
We can use dynamic programming to solve the subset sum problem efficiently. The idea is that if the total sum of the array is odd, it cannot be partitioned into two parts with equal sum. However, if it is even, we aim to find a subset whose sum equals half of the total sum of the array. This is so that two partitions (subset elements and excluded elements) have equal sums, which is half the total sum of the array.
This problem exhibits the property of optimal substructure, meaning the solution to a problem can be constructed from solutions to its subproblems. For each number, we decide whether to include it in the subset contributing to the target sum or not.
This problem is similar to the classic Subset Sum Problem, which is discussed in detail in a previous post – Subset Sum Problem
We define a 2D Dynamic Programming array dp[i][j] where i denotes the number of elements (starting from 0) considered and j represents the target sum. dp[i][j] is true if a sum j can be formed using the first i numbers.
Optimal Substructure
An optimal solution to problem contains optimal solution to subproblems. To consider all subset of items, 2 cases for every item arises:
- Item is included in solution set
- Item is not included in solution set
Therefore,
ifnums[i-1]> j: // j is the current sum
// nums[i-1] is not included, since it can’t be used to form sum j
dp[i][j] = dp[i-1][j]
else:
dp[i][j] = dp[i-1][j-nums[i-1]]OR dp[i-1][j]
This approach has time and space complexity of O(N * sum/2).
Code Implementation
bool canPartition(vector<int>& nums) {
int N = nums.size();
int totalSum = accumulate(nums.begin(), nums.end(), 0);
if (totalSum % 2 != 0) return false;
int target = totalSum / 2;
vector<vector<bool>> dp(N + 1, vector<bool>(target + 1, false));
for (int i = 0; i <= N; i++) dp[i][0] = true; // a subset with sum 0 is always possible (empty subset)
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= target; j++) {
dp[i][j] = dp[i - 1][j];
if (j >= nums[i - 1]) {
dp[i][j] = dp[i][j] || dp[i - 1][j - nums[i - 1]];
}
}
}
return dp[N][target];
}
Optimized Dynamic Programming
To reduce space, we can compress the 2D dynamic programming array into a 1D array. The idea is that for every new number, we update the dynamic programming table in reverse (from target down to number). Also, since for dp[i][j] we only need the previous row’s values (dp[i-1][j], dp[i-1][j-nums[i-1]]), we need not store values for all the previous rows.
Therefore, the optimal substructure becomes:
dp[j] = dp[j] OR dp[j-num]
dp[j]istrueif it was alreadytruebefore (ie. we could reach sumjwithoutnum)- OR if
dp[j-num]istrue, ie. we could reachj - numbefore and addingnumgives usj.
This optimization reduces space to O(sum/2), making the algorithm more space efficient.
Pseudocode
CAN-PARTITION-DP(nums[0..N-1])
1. totalSum ← sum of all elements
2. if totalSum is odd, return false
3. target ← totalSum / 2
4. dp[0..target] ← false
5. dp[0] ← true
6. for num in nums:
7. for j = target down to num:
8. dp[j] ← dp[j] OR dp[j - num]
9. return dp[target]
Code Implementation
bool canPartition(vector<int>& nums) {
int totalSum = accumulate(nums.begin(), nums.end(), 0);
if (totalSum % 2 != 0) return false;
int target = totalSum / 2;
vector<bool> dp(target + 1, false);
dp[0] = true;
for (int num : nums) {
for (int j = target; j >= num; j--) {
dp[j] = dp[j] || dp[j - num];
}
}
return dp[target];
}
Why update in reverse from target to num?
When we iterate from target down to num, we make sure that dp[j-num] still holds the value from the previous iteration, ie. before the current number num was considered. This ensures that each dp[j] is updated based on results from the prior iteration rather than using values updated modified during the current iteration.
This simulates the dp[i][j] = dp[i-1][j] || dp[i-1][j-num] behavior.
Consider this optimal substructure property from 2D dynamic programming table:
dp[i][j] = dp[i-1][j-nums[i-1]]OR dp[i-1][j]
Here,dp[i-1][j-nums[i-1]]or particularly "i-1" ensures that the current number nums[i-1] is only used with subset sums computed before it was considered — that is, from the previous row.
If we updated from num to target, we would incorrectly reuse values from the current iteration — which would mean including the same number multiple times, violating the constraint that each number must be used at most once.
Let’s understand this with an example:
nums = [2, 3]
target = 4
Check if there's a subset that adds up to 4 using each number in nums[] at most once.
Forward Traversal (Incorrect for 0/1 Subset Sum)
for num in nums:
for j = nums to target:
dp[j] ← dp[j] OR dp[j-num]
1. Initialize:
dp = [T, F, F, F, F]
2. Process num = 2 (forward from j = 2 to 4):
j = 2:
dp[2] = dp[2] || dp[0] = F || T = T
dp = [T, F, T, F, F]
j = 3:
dp[3] = dp[3] || dp[1] = F || F = F
dp = [T, F, T, F, F]
j = 4:
dp[4] = dp[4] || dp[2] = F || T = T ← [INCORRECT]
dp = [T, F, T, F, T]
This is incorrect because we happened to use num = 2 (nums[0]) twice, which is not allowed in 0/1 subset sum (each element can be used at most once).
Specifically, we have computed dp[4] using the value dp[2] = T, which was updated earlier in the same iteration ie. in the iteration processing nums[0] or num = 2. This means we're reusing the same number more than once, which is not allowed in the 0/1 subset formulation.
Therefore, in 1D approach, we get:
for num in nums:
for j = target down to num:
dp[j] ← dp[j] OR dp[j-num]
Hence, the entire solution can be computed using a single 1D array.
Time Complexity
The time complexity of dynamic programming solution is O(N * sum/2), which works well within the problem constraints.
Space Complexity
O(sum/2) – due to the use of a single 1D array (dp[]) of size sum/2 + 1.