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

1. Calculate the total sum: Find the sum of all elements in the input array nums. If the sum is odd, it's impossible to partition the array into two equal 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. dp[i] will be true if a subset with sum i is possible, and false otherwise.

4. Initialization: dp[0] is true because an empty subset always has a sum of 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 a subset with sum i - num is possible), then dp[i] becomes true (because we can add num to that subset to get a subset with sum i).

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

Explanation

The dynamic programming approach cleverly builds a solution bottom-up. It checks if a subset sum is achievable by considering each number and checking if adding it to previously achievable subset sums leads to new achievable sums. The process efficiently explores all possible subset combinations without explicitly generating them. The space optimization using a 1D array dp keeps track of only the necessary information, improving space efficiency.

Code

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

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

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

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

        return dp[targetSum];
    }
}

Complexity

• Time Complexity: O(n * sum), where n is the length of nums and sum is the total sum of elements in nums. This is because of the nested loops.

• Space Complexity: O(sum), where sum is the total sum of elements in nums. This is the space used by the dp array. In the worst case, sum could be close to the total sum of all the integers in the array.