#416 Partition Equal Subset Sum - Solution

The key idea behind Partition Equal Subset Sum is to determine whether the array can be divided into two subsets with the same total sum. First, compute the total sum of the array. If the sum is odd, it is impossible to split it into two equal subsets. Otherwise, the problem reduces to checking whether a subset exists with sum target = totalSum / 2.

This becomes a classic subset sum dynamic programming problem. You can use a boolean DP approach where dp[i] represents whether a subset with sum i can be formed from the given numbers. Iteratively update the DP array for each element while traversing from right to left to avoid reuse of the same number.

An optimized 1D DP solution reduces space usage while maintaining efficiency. The overall time complexity is O(n * target), where n is the number of elements, and space complexity can be reduced to O(target).

Approach	Time Complexity	Space Complexity
Dynamic Programming (Subset Sum)	O(n × target)	O(n × target)
Optimized 1D DP	O(n × target)	O(target)

Solutions (4)

Dynamic Programming Approach

This problem can be viewed as a variation of the subset sum problem. The idea is to determine if there is a subset of the given array whose sum is exactly half of the total sum. We use dynamic programming to store information about the previous computations, specifically a DP array where dp[i] indicates whether it's possible to achieve sum i using the elements of the array.

Time Complexity: O(N * target), where N is the number of elements in nums and target is half of the total sum.
Space Complexity: O(target), due to the DP array.

Python C++

1def canPartition(nums):
2    total_sum = sum(nums)
3    if total_sum % 2 != 0:
4        return False
5    target = total_sum // 2
6    dp = [False] * (target + 1)
7    dp[0] = True
8    for num in nums:
9        for i in range(target, num - 1, -1):
10            dp[i] = dp[i] or dp[i - num]
11    return dp[target]

Explanation

The code starts by calculating the total sum of the array. If this sum is odd, it's impossible to split it into two equal subsets, so it returns false. Otherwise, it computes the target sum as half of the total sum and initializes a DP array dp of size target + 1. The DP array keeps track of which sums can be formed with the numbers encountered so far. It iterates through each number, updating the DP array to indicate whether a subset including that number can achieve each possible sum. Finally, it checks if the target sum is achievable.

Recursive with Memoization Approach

This approach uses recursion along with memoization to solve the problem. We try to find a subset that totals half of the overall sum. As we attempt different combinations, we keep track of subproblem solutions we have already computed, which optimizes our solution by avoiding redundant computations.

Time Complexity: O(N * target), where N is the number of elements in nums and target is half of the total sum. The memoization ensures each unique call is computed only once.
Space Complexity: O(N * target) due to the recursive stack and memoization map.

Java C#

1using System;
2using System.Collections.Generic;
3
4public class Solution {
    public bool CanPartition(int[] nums) {
        int total_sum = 0;
        foreach (int num in nums) total_sum += num;
        if (total_sum % 2 != 0) return false;
        return CanPartition(nums, 0, total_sum / 2, new Dictionary<string, bool>());
    }

    private bool CanPartition(int[] nums, int index, int target, Dictionary<string, bool> memo) {
        if (target == 0) return true;
        if (index >= nums.Length) return false;
        string memoKey = index + "," + target;
        if (memo.ContainsKey(memoKey)) return memo[memoKey];
        bool result = CanPartition(nums, index + 1, target, memo) || (target >= nums[index] && CanPartition(nums, index + 1, target - nums[index], memo));
        memo[memoKey] = result;
        return result;
    }
}