We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Partition Equal Subset Sum

Number: 416

Difficulty: Medium

Paid? No

Companies: Amazon, Google, Meta, Microsoft, tcs, TikTok, Zoho, Flipkart, EPAM Systems, Yahoo, eBay, Bloomberg, Walmart Labs

Problem Description

Given an integer array, determine if it is possible to partition the array into two subsets such that the sum of the elements in both subsets is equal.

Key Insights

  • The total sum of the array must be even, otherwise, partitioning into two equal subsets is impossible.
  • The problem can be transformed into a "subset sum" problem where we need to check if there exists a subset of numbers that sums to half of the total sum.
  • A dynamic programming approach can efficiently decide if such a subset exists.

Space and Time Complexity

Time Complexity: O(n * target), where target is half of the total sum. Space Complexity: O(target), using a one-dimensional DP array.

Solution

First, compute the total sum of the array. If the total is odd, return false since an odd number cannot be equally partitioned. Next, set the target sum to half of the total. Use a dynamic programming array (dp) where dp[i] represents whether a subset with sum i is achievable. Initialize dp[0] as true because a subset sum of 0 is always possible. Then, for each number in the array, iterate through the dp array backwards from target to the number’s value and update dp[i] to true if dp[i - num] is true. Ultimately, if dp[target] is true, the array can be partitioned into two subsets with equal sum.

Code Solutions

# Python solution for Partition Equal Subset Sum

def canPartition(nums):
    # Calculate the total sum of the array
    total_sum = sum(nums)
    
    # If the total sum is odd, equal partition is not possible
    if total_sum % 2 != 0:
        return False
        
    # Set the target sum to half of the total sum
    target = total_sum // 2
    
    # Initialize dp array where dp[i] is True if a subset sum i is achievable
    dp = [False] * (target + 1)
    dp[0] = True  # Base case: subset sum of 0 is always possible
    
    # Iterate through each number in the array
    for num in nums:
        # Iterate backwards to avoid overwriting dp values needed for current iteration
        for i in range(target, num - 1, -1):
            # Update dp[i] if dp[i-num] is True
            if dp[i - num]:
                dp[i] = True
                
    # dp[target] is True if a subset adds up to target sum
    return dp[target]

# Example usage:
# print(canPartition([1, 5, 11, 5]))
← Back to All Questions