Partition Equal Subset Sum

13
1

Problem Statement

An array nums contains positive integers. Divide all array elements into two disjoint subsets so every element belongs to exactly one subset.

Return true when both subsets can have the same sum. Return false when no equal-sum partition exists. Subset sizes may differ.

Example 1

Input: nums = [1, 2, 3, 4]
Output: true
Explanation: Subsets [1, 4] and [2, 3] both have sum 5.

Example 2

Input: nums = [2, 2, 3, 5]
Output: false
Explanation: The total sum is 12, but no subset has the required sum 6.

Recursion

Two equal subset sums must each be equal to half of the total array sum. If the total sum is odd, an equal partition is impossible because the two subset sums must be integers. If the total sum is even, finding one subset with sum totalSum / 2 automatically leaves the same sum for the remaining elements.

Each array value gives us two choices: skip the value or take it into the target subset. The state solve(index, target) records whether elements from positions 0 through index can form the required target. The public method starts with the last index and half of the total sum because the complete array and target represent the original problem.

Algorithm

  • Calculate totalSum by adding every array value because an odd total makes an equal partition impossible.

  • Return false if totalSum is odd because it cannot be divided into two equal integer subset sums.

  • Set target = totalSum / 2 because finding one subset with this sum guarantees that the remaining elements have the same sum.

  • Start with solve(N - 1, target) because the initial state makes every array element available.

  • Return true when target == 0 because the required subset sum has been formed.

  • Compare nums[0] with target when index == 0 because only the first element remains available.

  • Explore the skip branch with the same target because the current element may not be needed.

  • Explore the take branch only when nums[index] <= target, then reduce the target by that value because the current element is included.

  • Return the logical OR of both branches because either choice can produce a valid subset.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Checks a target using values through one index.
bool solve(int index, int target, vector<int>& nums) {
// A zero target already forms the needed subset.
if (target == 0) {
return true;
}
// The first value is the final available choice.
if (index == 0) {
return nums[0] == target;
}
// Skipping preserves the target for earlier values.
bool notTaken = solve(index - 1, target, nums);
bool taken = false;
// Taking remains valid only inside the target.
if (nums[index] <= target) {
// Taking reduces the sum needed from earlier values.
taken = solve(
index - 1, target - nums[index], nums
);
}
// Either successful choice proves subset feasibility.
return notTaken || taken;
}
public:
// Checks for a partition with equal subset sums.
bool canPartition(vector<int>& nums) {
int totalSum = 0;
// The full sum determines the required half-sum.
for (int value : nums) {
totalSum += value;
}
// An odd total cannot split into equal integers.
if (totalSum % 2 != 0) {
return false;
}
int target = totalSum / 2;
int n = nums.size();
// The full array starts the take-or-skip search.
return solve(n - 1, target, nums);
}
};
// Driver code
int main() {
vector<int> nums = {1, 5, 11, 5};
Solution obj;
cout << boolalpha << obj.canPartition(nums);
return 0;
}

Note: Direct recursion may fail for large input values. Repeated subproblems create exponential work, so an online judge may report Time Limit Exceeded.

Complexity Analysis

Time Complexity: O(2N), where N is the number of array elements, because each index can create a take branch and a skip branch, forming a binary recursion tree of depth N.

Space Complexity: O(N), because the longest active recursion chain contains at most one call for each array index.

Memoization

Different decision paths can reach the same combination of index and target. Plain recursion solves the same state repeatedly, even though a given state always produces the same answer. Memoization avoids this repeated work by storing the result of each state after it is calculated.

A two-dimensional dp array stores the answer for every index and target combination. A value of -1 represents an uncalculated state, while 0 and 1 represent false and true. When the same state is reached again, its stored result can be returned immediately instead of rebuilding the recursive subtree.

Algorithm

  • Perform the same parity check and calculate the half-sum target because memoization only optimizes the recursive search.

  • Create a dp table with N rows and target + 1 columns, filling it with -1 so every uncalculated state has a clear marker.

  • Start with solve(N - 1, target) because the complete array and required half-sum form the initial state.

  • Return true when target == 0 because the required subset sum has been formed.

  • Handle the index == 0 case by comparing nums[0] with target because only the first element remains available.

  • Return dp[index][target] when it is already calculated so repeated states avoid another recursive expansion.

  • Calculate skip = solve(index - 1, target) because the current element can be excluded from the subset.

  • Calculate take = solve(index - 1, target - nums[index]) when nums[index] <= target because the current element can be included in the subset.

  • Store skip || take in dp[index][target] because the target is possible if either choice forms a valid subset.

  • Return dp[index][target] so the calculated result can be reused by future calls.

Dry Run

Diagram 1
1 / 2

Diagram 1

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
private:
// Checks one state and stores the calculated answer.
bool solve(
int index,
int target,
vector<int>& nums,
vector<vector<int>>& dp
) {
// A zero target already forms the needed subset.
if (target == 0) {
return true;
}
// The first value is the final available choice.
if (index == 0) {
return nums[0] == target;
}
// A stored state avoids repeated recursion.
if (dp[index][target] != -1) {
return dp[index][target] == 1;
}
// Skipping preserves the target for earlier values.
bool notTaken = solve(
index - 1, target, nums, dp
);
bool taken = false;
// Taking remains valid only inside the target.
if (nums[index] <= target) {
// Taking reduces the sum needed from earlier values.
taken = solve(
index - 1,
target - nums[index],
nums,
dp
);
}
// The cache stores the combined decision result.
dp[index][target] = notTaken || taken;
return dp[index][target] == 1;
}
public:
// Checks for a partition with equal subset sums.
bool canPartition(vector<int>& nums) {
int totalSum = 0;
// The full sum determines the required half-sum.
for (int value : nums) {
totalSum += value;
}
// An odd total cannot split into equal integers.
if (totalSum % 2 != 0) {
return false;
}
int target = totalSum / 2;
int n = nums.size();
// Unknown states begin with a distinct marker.
vector<vector<int>> dp(
n, vector<int>(target + 1, -1)
);
// The full array starts the cached search.
return solve(n - 1, target, nums, dp);
}
};
// Driver code
int main() {
vector<int> nums = {1, 5, 11, 5};
Solution obj;
cout << boolalpha << obj.canPartition(nums);
return 0;
}

Complexity Analysis

Time Complexity: O(N × target), where N is the number of array elements, because each index-and-remaining-sum state is evaluated at most once with constant transition work.

Space Complexity: O(N × target) + O(N), because the dp table stores all index-and-sum states, while the recursion stack can contain up to N calls.

Tabulation

Memoization discovers states only after recursive calls request answers. Tabulation removes the call stack by filling the same dp[index][sum] states from smaller indices toward larger indices.

Every row describes subset sums available through one array index. Sum 0 stays reachable without selecting a value. The first row can additionally reach nums[0], and each later row combines the same skip and take choices used by recursion.

Algorithm

  • Begin with the total-sum parity check because an odd total has no equal integer split.

  • Create a boolean dp table with n rows and target + 1 columns so every recursive state has an iterative counterpart.

  • Mark dp[index][0] as true for every row because an empty selection always forms sum 0.

  • Mark dp[0][nums[0]] when the first value fits because the first row has only one non-empty subset choice.

  • Move from index 1 toward n - 1 so the previous row is complete before any current-row transition needs earlier answers.

  • Read the skip and valid take results from the previous row so both recursive choices use states built without the current value.

  • Store the logical OR of both choices and return dp[n - 1][target] because the final state covers every available value.

Dry Run

partition-equal-subset-sum-tabulation.png

partition-equal-subset-sum-tabulation.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Checks for a partition with equal subset sums.
bool canPartition(vector<int>& nums) {
int totalSum = 0;
// The full sum determines the required half-sum.
for (int value : nums) {
totalSum += value;
}
// An odd total cannot split into equal integers.
if (totalSum % 2 != 0) {
return false;
}
int target = totalSum / 2;
int n = nums.size();
// Each cell records one subset-sum state.
vector<vector<bool>> dp(
n, vector<bool>(target + 1, false)
);
// Sum zero needs no selected value.
for (int index = 0; index < n; index++) {
dp[index][0] = true;
}
// The first value forms one reachable sum.
if (nums[0] <= target) {
dp[0][nums[0]] = true;
}
// Later rows use only completed previous rows.
for (int index = 1; index < n; index++) {
for (int sum = 1; sum <= target; sum++) {
// Skipping keeps the previous-row result.
bool notTaken = dp[index - 1][sum];
bool taken = false;
// Taking remains valid only inside the sum.
if (nums[index] <= sum) {
// Taking extends a previous reachable sum.
taken = dp[index - 1][sum - nums[index]];
}
// Either choice can make the sum reachable.
dp[index][sum] = notTaken || taken;
}
}
// The last state covers the full array.
return dp[n - 1][target];
}
};
// Driver code
int main() {
vector<int> nums = {1, 5, 11, 5};
Solution obj;
cout << boolalpha << obj.canPartition(nums);
return 0;
}

Complexity Analysis

Time Complexity: O(N × target), where N is the number of array elements, because every index-and-sum state is calculated once with constant work using values from the previous row.

Space Complexity: O(N × target), because the two-dimensional dp table stores one boolean for every index-and-sum state, and no recursion stack is used.

Space Optimization

Every tabulation state reads only from the previous row. Rows older than the previous row never affect a new answer, so the full table can shrink to two one-dimensional arrays.

Array previous represents subset sums before the current value. Array current receives every take-or-skip result for the current value. After a row is complete, assigning current to previous shifts the newest answers forward for the next value.

Algorithm

  • Begin with the parity check and half-sum target because the space improvement leaves the partition reduction unchanged.

  • Create previous with target + 1 booleans so one array can represent the first tabulation row.

  • Mark sum 0 and the fitting first value as reachable because both entries form the base row.

  • Create a fresh current array for every later value so updates never overwrite states still needed from previous.

  • Calculate each current[sum] from skip and valid take results in previous so the current value contributes at most once.

  • Shift current into previous only after every sum is processed so one array value cannot be selected more than once.

  • Return previous[target] after the final shift because the retained row represents all available values.

Dry Run

partition-equal-subset-sum-space-optimization.png

partition-equal-subset-sum-space-optimization.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
// Checks for a partition with equal subset sums.
bool canPartition(vector<int>& nums) {
int totalSum = 0;
// The full sum determines the required half-sum.
for (int value : nums) {
totalSum += value;
}
// An odd total cannot split into equal integers.
if (totalSum % 2 != 0) {
return false;
}
int target = totalSum / 2;
int n = nums.size();
// The first row begins with only sum zero.
vector<bool> previous(target + 1, false);
previous[0] = true;
// The first value forms one reachable sum.
if (nums[0] <= target) {
previous[nums[0]] = true;
}
// Each new value builds one independent row.
for (int index = 1; index < n; index++) {
vector<bool> current(target + 1, false);
current[0] = true;
for (int sum = 1; sum <= target; sum++) {
// Skipping keeps the previous-row result.
bool notTaken = previous[sum];
bool taken = false;
// Taking remains valid only inside the sum.
if (nums[index] <= sum) {
// Taking extends a previous reachable sum.
taken = previous[sum - nums[index]];
}
// The current state merges both valid choices.
current[sum] = notTaken || taken;
}
// Shift the completed row into the next iteration.
previous = current;
}
// The retained row covers the full array.
return previous[target];
}
};
// Driver code
int main() {
vector<int> nums = {1, 5, 11, 5};
Solution obj;
cout << boolalpha << obj.canPartition(nums);
return 0;
}

Complexity Analysis

Time Complexity: O(N × target), where N is the number of array elements, because each of the N elements checks every possible sum from 0 to target with constant transition work.

Space Complexity: O(target), because previous and current each store one boolean for every possible sum, and no older rows are retained.

Interview follow-up Questions

No. Equal sums are the only balance condition. For nums = [1, 5, 5, 11], subsets [1, 5, 5] and [11] have different sizes but equal sums.

Dynamic ProgrammingTCS NQT

Read Similar Blogs

Comments0