Partition Equal Subset Sum

Leetcode Problem:

• Partition Equal Subset Sum

Summary

• Given an integer array, determine if it can be partitioned into two subsets with equal sum.

Approach

• Dynamic Programming: The solution uses a dynamic programming approach to build a table (dp) where dp[i] represents whether the sum of the first i elements can be achieved
• The solution iterates through the array, updating the dp table and checking for the target sum.

Complexity

• O(n * targetSum) where n is the length of the array and targetSum is the target sum

Explanation

• The solution first calculates the total sum of the array and checks if it is even
• If it is not, the array cannot be partitioned into two subsets with equal sum
• Otherwise, it initializes a dynamic programming table dp of size targetSum + 1, where dp[i] represents whether the sum of the first i elements can be achieved
• It then iterates through the array, updating the dp table and checking for the target sum
• If the target sum can be achieved, the function returns true
• If not, the function returns false.

Solution Code:

class Solution {
public:
    bool canPartition(vector& nums) {
        int totalSum = 0;
        for (int num : nums) totalSum += num;

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

        int targetSum = totalSum / 2;
        vector dp(targetSum + 1, false);
        dp[0] = true;
        for (int num : nums) {
            for (int currSum = targetSum; currSum >= num; --currSum) {
                dp[currSum] = dp[currSum] || dp[currSum - num];
                if (dp[targetSum]) return true;
            }
        }
        return dp[targetSum];
    }
};