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 equal-sum subsets, 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 initialized to false. dp[i] will be true if a subset with sum i is possible, otherwise false.

4. Base case: dp[0] = true (an empty subset has a sum of 0).

5. Iteration: Iterate through the input array nums. For each number num, iterate through the dp array from targetSum down to num. If dp[i - num] is true (meaning a subset with sum i - num exists), then dp[i] can be set to true (because we can add num to that subset to get a sum of i).

6. Result: After iterating through all numbers, dp[targetSum] will be true if a subset with the target sum exists, and false otherwise. Return dp[targetSum].

Explanation

The dynamic programming approach efficiently explores all possible subset combinations. The inner loop iterates backward to avoid double-counting subsets. For each number, it checks if including that number in a subset would lead to a valid subset sum. The dp array acts as a memoization table, storing whether a given sum is achievable.

Code (TypeScript)

function canPartition(nums: number[]): boolean {
    const totalSum = nums.reduce((sum, num) => sum + num, 0);
    if (totalSum % 2 !== 0) {
        return false;
    }
    const targetSum = totalSum / 2;
    const dp: boolean[] = new Array(targetSum + 1).fill(false);
    dp[0] = true;

    for (const num of nums) {
        for (let 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 number of elements in nums and S is the targetSum (approximately half of the total sum). The nested loops dominate the runtime.
• Space Complexity: O(S), The space used by the dp array is proportional to the targetSum.