Partition Equal Subset Sum

Problem Description

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.

Examples

Constraints

• 1 ≤ nums.length ≤ 200
• 1 ≤ nums[i] ≤ 100

Subset Sum to Half of the Total

The problem is equivalent to finding if there exists a subset of nums that sums to exactly target = total_sum / 2. If total_sum is odd, we can immediately return false.

Let dp[i] be true if a subset sum of i can be formed, and false otherwise.

• Initialize dp[0] = true (an empty subset has sum 0).
• For each number num in nums, we update our DP array from right to left: dp[i] = dp[i] || dp[i - num] for i from target down to num.

Updating from right to left ensures that each number from the array is used at most once in a subset.

Solution: 1D DP Array

class Solution {
    public boolean canPartition(int[] nums) {
        int total = 0;
        for (int num : nums) total += num;

        if (total % 2 != 0) return false; // odd sum cannot be divided equally
        int target = total / 2;

        boolean[] dp = new boolean[target + 1];
        dp[0] = true;

        for (int num : nums) {
            for (int i = target; i >= num; i--) {
                dp[i] = dp[i] || dp[i - num];
            }
            if (dp[target]) return true; // early exit optimization
        }

        return dp[target];
    }
}

class Solution:
    def canPartition(self, nums: list[int]) -> bool:
        total = sum(nums)
        if total % 2 != 0:
            return False

        target = total // 2
        dp = [False] * (target + 1)
        dp[0] = True

        for num in nums:
            # loop backwards to avoid using the same element multiple times
            for i in range(target, num - 1, -1):
                dp[i] = dp[i] or dp[i - num]
            if dp[target]:
                return True

        return dp[target]

#include <vector>
#include <numeric>
#include <algorithm>

class Solution {
public:
    bool canPartition(std::vector<int>& nums) {
        int total = std::accumulate(nums.begin(), nums.end(), 0);
        if (total % 2 != 0) return false;

        int target = total / 2;
        std::vector<bool> dp(target + 1, false);
        dp[0] = true;

        for (int num : nums) {
            for (int i = target; i >= num; i--) {
                dp[i] = dp[i] || dp[i - num];
            }
            if (dp[target]) return true;
        }

        return dp[target];
    }
};

Complexity Analysis:

• Time Complexity: O(N * T) where N is the length of nums and T is the target sum (total / 2). The nested loop bounds the complexity. Given constraints, N ≤ 200 and T ≤ 10000, so total iterations is at most 2 * 10⁶, which runs in milliseconds.
• Space Complexity: O(T) to store the 1D DP array.

Common Mistakes

• Looping from left to right. If you loop i from num to target, you’ll allow the same number to be reused multiple times to form a sum (equivalent to the Unbounded Knapsack problem, or Coin Change). We must loop from target down to num to ensure each number is used at most once.

← All Problems