Partition Equal Subset Sum Modification - Google
Anonymous User
1382
ArrayGoogleInterview

Recently was asked a modified version of
416. Partition Equal Subset Sum (with negative numbers possible)

Initial question: 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. Numbers can be negative.

Bruteforce'

def canPartition(nums):
    total_sum = sum(nums)
    
    # If total sum is odd, can't partition into two equal subsets
    if total_sum % 2 != 0:
        return False
    
    target = total_sum // 2
    possible_sums = {0}  # Start with 0 as a possible sum
    
    for num in nums:
        if num > target:
            continue
        new_sums = set()
        for s in possible_sums:
            new_sum = s + num
            if new_sum == target:
                return True
            if new_sum < target:
                new_sums.add(new_sum)
        possible_sums.update(new_sums)
    
    return target in possible_sums

Maybe we can modify the range of sum we take in LC 416 to include negative numbers in loop 2 we check for targets. something like offset?

Follow up: Return the both the subset.

Follow up 2: Later we can discuss how to return all such partition.

can someone post the optimized solution?

Comments (4)