416. Partition Equal Subset Sum

📝 Problem Details

• Title: 416. Partition Equal Subset Sum
• Link: https://leetcode.com/problems/partition-equal-subset-sum/
• Difficulty: Medium
• Tags/Categories: Dynamic-Programming

input integer array nums return true if you can partition the array into two subsets the sum of the elements in the two subsets is equal return false otherwise

💡 Explanation of Solution

- iterative (bottom-up) dp approach
	- boolean dp array to store whether each possible sum up to the target value can be achieved
	- fill out the dp table starting from smaller subproblems (dp[0] = True) and building up to target (dp[target])
	- transition is dp[i] = dp[i] or dp[i - num] , working backward from target down to num to ensure we dont reuse numbers in the same iteration

⌛ Complexity Analysis

Time Complexity : O(n * target)
Space Complexity: O(target)

💻 Implementation of Solution

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int totalSum = accumulate(nums.begin(), nums.end(), 0);
        // early exit if total sum is odd since we know we cant form 2 equal subsets
        if(totalSum % 2 != 0) return false;
        int target = totalSum / 2;
 
        vector<bool> dp (target+1, false);
        dp[0] = true; // base case for a sum of 0
 
        for(int num : nums) {
            for (int i = target; i >= num; i--) { // traverse backwards to avoid reuse
                /*
                    Transition statement:
                    If `dp[i - num]` is `true`, it means a subset sum `i - num` is possible.
                    Since we are adding `num`, that means sum `i` is now also possible.
                */
                
                dp[i] = dp[i] || dp[i - num];
            }
        }
        return dp[target];
    }
};