Partition Equal Subset Sum medium

Problem Statement

Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Example 1:

Input: nums = [1,5,11,5] Output: true Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: nums = [1,2,3,5] Output: false Explanation: The array cannot be partitioned into equal sum subsets.

Steps to Solve

1. Calculate the total sum: Find the sum of all elements in the input array. If the sum is odd, it's impossible to partition the array into two subsets with equal sums, so return false.

2. Target Sum: The target sum for each subset is totalSum / 2.

3. Dynamic Programming: Use a boolean array dp of size targetSum + 1. dp[i] will be true if there exists a subset of numbers from nums that sums up to i, and false otherwise.

4. Initialization: dp[0] = true (an empty subset sums to 0).

5. Iteration: Iterate through the nums array. For each number num, iterate through the dp array from targetSum down to num. If dp[i - num] is true (meaning there's a subset summing to i - num), then dp[i] can also be true (by adding num to that subset).

6. Result: After iterating through all numbers, dp[targetSum] will indicate whether a subset with the target sum exists. Return dp[targetSum].

Explanation

The dynamic programming approach efficiently checks all possible combinations of subsets. Instead of explicitly generating all subsets (which would be exponential time complexity), it builds up a solution incrementally. dp[i] acts as a memoization table, storing whether a sum i is achievable using a subset of the numbers encountered so far. By iterating downwards from targetSum, we ensure that we're only considering subsets using numbers encountered in the current iteration.

Code (C#)

using System;

public class Solution {
    public bool CanPartition(int[] nums) {
        int totalSum = 0;
        foreach (int num in nums) {
            totalSum += num;
        }

        if (totalSum % 2 != 0) {
            return false;
        }

        int targetSum = totalSum / 2;
        bool[] dp = new bool[targetSum + 1];
        dp[0] = true;

        foreach (int num in nums) {
            for (int i = targetSum; i >= num; i--) {
                dp[i] = dp[i] || dp[i - num];
            }
        }

        return dp[targetSum];
    }
}

Complexity

• Time Complexity: O(N * S), where N is the length of nums and S is the targetSum (which is approximately half the total sum of nums).
• Space Complexity: O(S), the space used by the dp array.