algoadvance

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

Example 1:

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11],

Example 2:

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

Constraints:

Clarifying Questions:

  1. Can nums contain duplicate numbers?
    • Yes, nums can contain duplicates.
  2. Can the array have only one element?
    • Yes, but in that case, the answer is trivially false since a single element cannot be partitioned.
  3. Are all elements guaranteed to be positive integers?
    • Yes, as stated in the constraints.

Strategy:

This problem can be approached using dynamic programming (DP). The idea is:

  1. Calculate the total sum of the array. If this sum is odd, it’s not possible to partition the array into two equal subsets.
  2. If the total sum is even, let’s call half of this sum target.
  3. Use a DP array dp where dp[i] will be True if a subset with sum i can be formed using the elements of the array.
  4. Initialize the DP array such that dp[0] is True because a sum of 0 can always be formed (with the empty subset).
  5. Iterate over the elements in nums and update the DP array backwards (to avoid using the same element more than once in the subset).

Code:

def canPartition(nums):
    total_sum = sum(nums)
    
    # If the total sum is odd, it's not possible to partition into two equal subsets
    if total_sum % 2 != 0:
        return False
    
    target = total_sum // 2
    n = len(nums)
    
    # Initialize a DP array of size target + 1
    dp = [False] * (target + 1)
    dp[0] = True  # We can always form a zero sum with an empty subset
    
    # Update the dp array for each number in nums
    for num in nums:
        for i in range(target, num - 1, -1):
            dp[i] = dp[i] or dp[i - num]
    
    # The answer will be whether we can form the target sum using elements of nums
    return dp[target]

# Example usage:
print(canPartition([1, 5, 11, 5]))  # Output: True
print(canPartition([1, 2, 3, 5]))   # Output: False

Time Complexity:

The time complexity of this solution is (O(n \times target)), where n is the number of elements in nums and target is half the sum of elements in nums. Here:

Try our interview co-pilot at AlgoAdvance.com