Medium

Partition Equal Subset Sum

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

Input:nums = [1,5,11,5]

Output:true

The array can be partitioned as [1, 5, 5] and [11]. The sum of both subsets is 11.

Input:nums = [1,2,3,5]

Output:false

The array cannot be partitioned into equal sum subsets.

Constraints

1 <= nums.length <= 200
1 <= nums[i] <= 100

Dynamic Programming (0/1 Knapsack)

Approach

This problem is a variation of the 0/1 Knapsack problem. First, calculate the total sum of the array. If the sum is odd, it cannot be partitioned into two equal subsets, so return false. If the sum is even, we need to find if there exists a subset whose sum is exactly `target = sum / 2`. We use a set (or boolean array) to keep track of all possible sums we can generate using elements processed so far. For each number in `nums`, we iterate through our current set of reachable sums and add the new number to each of them to find new reachable sums. If we ever generate the `target`, we return true.

Complexity Analysis

Time Complexity

O(n * sum(nums))

Space Complexity

O(sum(nums))

Time complexity is bounded by the number of elements times the maximum possible sum we can reach (which is half the total sum). Space complexity is proportional to the target sum to store the reachable sums in the set.

Solution.java

1class Solution {2    public boolean canPartition(int[] nums) {3        int sum = 0;4        for (int num : nums) {5            sum += num;6        }7        8        // If sum is odd, cannot be divided equally9        if (sum % 2 != 0) {10            return false;11        }12        13        int target = sum / 2;14        Set<Integer> dp = new HashSet<>();15        dp.add(0);16        17        for (int num : nums) {18            Set<Integer> nextDp = new HashSet<>();19            for (int t : dp) {20                if (t + num == target) {21                    return true;22                }23                nextDp.add(t + num);24                nextDp.add(t);25            }26            dp = nextDp;27        }28        29        return dp.contains(target);30    }31}