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
totalSumby adding every array value because an odd total makes an equal partition impossible.Return
falseiftotalSumis odd because it cannot be divided into two equal integer subset sums.Set
target = totalSum / 2because 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
truewhentarget == 0because the required subset sum has been formed.Compare
nums[0]withtargetwhenindex == 0because 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
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 codeint 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
dptable withNrows andtarget + 1columns, filling it with-1so 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
truewhentarget == 0because the required subset sum has been formed.Handle the
index == 0case by comparingnums[0]withtargetbecause 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])whennums[index] <= targetbecause the current element can be included in the subset.Store
skip || takeindp[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
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 codeint 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
dptable withnrows andtarget + 1columns so every recursive state has an iterative counterpart.Mark
dp[index][0]astruefor every row because an empty selection always forms sum0.Mark
dp[0][nums[0]]when the first value fits because the first row has only one non-empty subset choice.Move from index
1towardn - 1so 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
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 codeint 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
previouswithtarget + 1booleans so one array can represent the first tabulation row.Mark sum
0and the fitting first value as reachable because both entries form the base row.Create a fresh
currentarray for every later value so updates never overwrite states still needed fromprevious.Calculate each
current[sum]from skip and valid take results inpreviousso the current value contributes at most once.Shift
currentintopreviousonly 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
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 codeint 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.
Be the first to add a comment.