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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Partition Equal Subset Sum

Difficulty: Medium

Problem Description

Given an integer array nums, return true if you can partition the array into two subsets such that the sum of the elements in both subsets is equal or false otherwise.

Key Insights

  • The problem can be reduced to checking if there exists a subset of nums that sums to total/2, where total is the sum of all elements in nums.
  • If total is odd, it's immediately impossible to partition it into two equal subsets.
  • We can use dynamic programming to solve this problem, where we maintain a boolean array to track achievable subset sums.

Space and Time Complexity

Time Complexity: O(n * target), where n is the number of elements in nums and target is total/2.
Space Complexity: O(target), where target is total/2.

Solution

We will use a dynamic programming approach. We will create a boolean array dp where dp[j] will be true if a subset with sum j can be formed using the elements of nums. We will iterate through each number in nums and update our dp array accordingly.

Code Solutions

def canPartition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    dp = [False] * (target + 1)
    dp[0] = True  # A sum of 0 is always possible

    for num in nums:
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]

    return dp[target]
← Back to All Questions