DSA

Partition Equal Subset Sum

Tabulation approach. Optimal — Time O(n*k), Space O(k).

August 8, 2026
DSADynamic ProgrammingDPLeetCodePracticeBacktrackingRecursion

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.

Practice Link

Intuition#

If we can split the array into two subsets with equal sum, each subset must sum to exactly totalSum / 2. So the problem reduces to the classic Subset Sum problem: does any subset of the array sum to totalSum / 2? If total sum is odd, it's immediately impossible (no integer half-sum exists). Otherwise, run a 0-1 knapsack-style DP to check reachability.

  • Find the total sum of the array.
  • If the total sum is odd, two subsets with equal sum cannot exist — return false.
  • Find totalSum / 2 and use the Subset Sum Equal to Target DP approach.
  • If that target sum is reachable → two equal-sum subsets exist.

Tabulation Solution#

dp[i][j] = can we pick a subset from the first i elements that sums to j. For each element, either skip it (dp[i-1][j]) or include it (dp[i-1][j - nums[i]] if nums[i] \<= j).

cpp
class Solution {
public:

    int findTotalSum(vector<int>& nums)
    {
        int sum =0;
        for(int num: nums)
            sum += num;
        return sum;
    }

    bool canPartition(vector<int>& nums) {
        int totalSum = findTotalSum(nums);
        if(totalSum%2!=0)
            return false;

        int n = nums.size();
        int subsetSum = totalSum/2;
        vector<vector<bool>> dp(n, vector<bool> (subsetSum+1, false));

        for(int i=0;i<n;i++)
            dp[i][0]= true;

        if(nums[0] <= subsetSum)
            dp[0][nums[0]] = true;

        for(int i=1;i<n;i++)
        {
            for(int j=1;j<=subsetSum;j++)
            {
                bool not_take = dp[i-1][j];
                bool take = false;

                if(nums[i]<= j)
                    take = dp[i-1][j-nums[i]];
                dp[i][j] = take || not_take;
            }
        }

        return dp[n-1][subsetSum];
    }
};

Time Complexity - O(n*k)

Space Complexity - O(n*k )

Space Optimized#

Since row i only depends on row i-1, replace the full 2D table with two 1D boolean arrays (prev and curr). After each item, swap curr into prev. Space drops from O(n×k) to O(k).

cpp
class Solution {
public:

    int findTotalSum(vector<int>& nums)
    {
        int sum =0;
        for(int num: nums)
            sum += num;
        return sum;
    }

    bool canPartition(vector<int>& nums) {
        int totalSum = findTotalSum(nums);
        if(totalSum%2!=0)
            return false;

        int n = nums.size();
        int subsetSum = totalSum/2;
        vector<bool> prev(subsetSum+1, false);
        vector<bool> curr(subsetSum+1, false);

        prev[0] = true;
        if(nums[0] <= subsetSum)
            prev[nums[0]] = true;

        for(int i=1;i<n;i++)
        {
            curr[0] = true;
            for(int j=1;j<=subsetSum;j++)
            {
                bool not_take = prev[j];
                bool take = false;

                if(nums[i]<= j)
                    take = prev[j-nums[i]];
                curr[j] = take || not_take;
            }
            prev = curr;
        }

        return curr[subsetSum];
    }
};

Time Complexity - O(n*k)

Space Complexity - O(k)

Related articles

DSASubsets with sum kCovers: Recursive, Memoized. Optimal — Time O(n*k), Space O(n*k).DSASubset Sum equal to targetCovers: Recursion, Memoized, Tabulation. Optimal — Time O(n*k), Space O(n*k ).DSAGenerate ParenthesesGenerate all combinations of well-formed parentheses using backtracking. Optimal — Time O(4ⁿ/√n), Space O(n).6 min read