Subset Sum

Problem Overview

The problem at hand is a well-known challenge related to partitioning and dynamic programming. The task is defined as follows: Given a non-empty array nums containing positive integers, determine if the array can be partitioned into two subsets whose sums are equal.

Understanding the Problem

To break this problem down, consider an array like [1, 5, 11, 5]. Our goal is to figure out whether we can divide this array into subsets with equal sum. In this instance, we can form [1, 5, 5] and [11], both of which sum to 11.

The immediate thought might be about finding combinations and checking sums, but with an optimal approach, we aim to utilize dynamic programming (DP) to solve it efficiently.

Key Observation:

• If the total sum of the array is odd, it's immediately impossible to split it into two equal parts.
• If the sum is even, say 2 * target, then our task reduces to finding a subset of the array that sums to target.

Key DSA Concepts and Theory

Dynamic Programming (DP): This is a method for solving complex problems by breaking them down into smaller subproblems, solving each subproblem just once, and storing their solutions. This technique is particularly powerful for optimization problems.

For the partition problem, DP helps in finding if a subset with a particular sum exists. This boils down to a classic DP problem: the "subset sum problem", where we check whether any subset of numbers adds up to a specific target.

DP Array Definition in this Case:

• dp[i] will be true if a subset with sum i can be formed from the elements.

Solution Approach

Step-by-Step Plan

1. Early Pruning:

   • Calculate the total sum. If it is odd, immediately return false.

2. Define the Target:

   • If the sum is even, define target as half of total sum: sum / 2.

3. Initialize a DP Array:

   • Create a boolean array dp of size target + 1, initialized to false.
   • Set dp[0] = true because a sum of 0 can always be achieved with an empty subset.

4. Fill the DP Array:

   • For each number in the array nums:
     • Traverse backwards from target down to the number.
     • If dp[j - num] is true, then dp[j] should also be true.

5. Final Decision:

   • At the end of processing, if dp[target] is true, a subset with the desired sum exists, hence return true.

C++ Code Implementation

#include <vector>
#include <numeric>

class Solution {
public:
    bool canPartition(std::vector<int>& nums) {
        int sum = std::accumulate(nums.begin(), nums.end(), 0);

        // If sum is odd, can't split equally
        if (sum % 2 != 0) return false;

        int target = sum / 2;
        std::vector<bool> dp(target + 1, false);
        dp[0] = true; // Base case: 0 sum achievable with empty subset

        for (int num : nums) {
            for (int j = target; j >= num; --j) {
                if (dp[j - num]) {
                    dp[j] = true;
                }
            }
        }

        return dp[target];
    }
};

Java Code Implementation

import java.util.Arrays;

class Solution {
    public boolean canPartition(int[] nums) {
        int sum = Arrays.stream(nums).sum();
        
        // If sum is odd, can't split equally
        if (sum % 2 != 0) return false;

        int target = sum / 2;
        boolean[] dp = new boolean[target + 1];
        dp[0] = true; // Base case: 0 sum achievable with empty subset

        for (int num : nums) {
            for (int j = target; j >= num; --j) {
                if (dp[j - num]) {
                    dp[j] = true;
                }
            }
        }

        return dp[target];
    }
}

Time and Space Complexity Analysis

• Time Complexity: The time complexity is O(n * target) where n is the number of elements in nums and target is half the sum of nums. This is because we iterate through each number and check up to the target sum.

• Space Complexity: The space complexity is O(target) due to the dp array's size.

Common Mistakes to Avoid

1. Not Checking Sum Parity: Make sure to first check if the total sum is odd — an odd total sum means immediate impossibility to partition equally.
2. Incorrect DP Array Updates: Avoid updating the dp array in a forward manner as it may lead to incorrect results due to overwriting.

Similar Problems on LeetCode

• 416. Partition Equal Subset Sum
• 494. Target Sum
• 698. Partition to K Equal Sum Subsets

Additional Resources and References

• Dynamic Programming on LeetCode
• Textbooks on algorithm design for deeper understanding of dynamic programming.
• Online resources like Khan Academy or MIT's OpenCourseWare for conceptual overviews of dynamic programming and related problems.