algoadvance

Leetcode 416. Partition Equal Subset Sum

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 the elements in both subsets is equal.

Clarifying Questions

Before jumping into the solution, let’s consider some clarifying questions that could help understand edge cases and constraints better:

  1. Can the array contain zero?
    • No, the array contains only positive integers.
  2. What is the range of the length of the array and the values within it?
    • Typical constraints for such problems are:
      • 1 <= nums.length <= 200
      • 1 <= nums[i] <= 100
  3. Is there a specific time complexity requirement?
    • While not specified, an efficient solution is desirable. We’ll aim for a pseudo-polynomial time complexity solution using dynamic programming.

Strategy

To determine if the array can be partitioned into two subsets with equal sum:

  1. Total Sum Check:
    • Calculate the total sum of the array elements. If this sum is odd, it’s impossible to split it into two equal subsets.
  2. Target Sum for Each Subset:
    • If the total sum is even, the target sum for each subset will be total_sum / 2.
  3. Dynamic Programming Approach:
    • We’ll use a 1D dynamic programming array (dp) where dp[i] will be true if a subset sum of i can be achieved with the elements processed so far.
    • Initialize dp[0] to true because a sum of 0 is always possible (with an empty subset).
    • Iterate through each number in the array and update the dp array from the end to the start to prevent using the same element multiple times.

Code

#include <vector>
#include <numeric>
#include <iostream>

class Solution {
public:
    bool canPartition(std::vector<int>& nums) {
        int totalSum = std::accumulate(nums.begin(), nums.end(), 0);
        // If the total sum is odd, it can't be divided into two equal subsets
        if (totalSum % 2 != 0) return false;
        
        int target = totalSum / 2;
        std::vector<bool> dp(target + 1, false);
        
        // A subset sum of 0 is always possible with an empty subset
        dp[0] = true;
        
        for (const int& num : nums) {
            // Update dp array from end to start to avoid reusing the same element
            for (int i = target; i >= num; --i) {
                dp[i] = dp[i] || dp[i - num];
            }
        }
        
        return dp[target];
    }
};

int main() {
    Solution sol;
    std::vector<int> nums = {1, 5, 11, 5};
    bool canPartition = sol.canPartition(nums);
    std::cout << (canPartition ? "True" : "False") << std::endl;  // Output: True
    return 0;
}

Time Complexity

This solution efficiently checks the possibility of partitioning the array into two subsets with equal sums using dynamic programming.

Cut your prep time in half and DOMINATE your interview with AlgoAdvance AI