A LeetCode Daily Series — Day 71

Today’s problem is called "Partition Equal Subset Sum"

Updated: at 06:15 PM

Welcome to another problem-solving journey in the world of algorithms! In this article, we’re going to delve into a particularly intriguing problem known as “Partition Equal Subset Sum.” Don’t worry if you’re new to the concept; we’ll guide you through understanding the problem, exploring various approaches to solving it, and finally, we’ll provide you with an efficient solution, perfect for beginners.

If you’re just joining us, it might be helpful to catch up on the previous entries. Want to see more problem-solving techniques? Follow me here on my blog!

Cover Image

Understanding the Problem

Before we dive into solving the problem, let’s make sure we understand it clearly. Given an integer array nums, our task is to determine whether it’s possible to partition the array into two subsets such that the sum of the elements in both subsets is equal. In simpler terms, we want to split the array into two parts, where the sum of the elements in each part is the same.

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.

Approach 1: Dynamic Programming

Dynamic programming offers an efficient way to solve this problem by breaking it down into simpler subproblems. Here we exhaustively search through all possible subsets of the given array. We start with an empty subset and iteratively add each element of the array to all existing subsets, generating new subsets. We then check if any subset’s sum equals half of the total sum of the array, indicating a valid partition.

def canPartition(self, nums: List[int]) -> bool:
    if sum(nums) % 2:
        return False

    dp = set()
    dp.add(0)

    target = sum(nums) // 2

    for i in range(len(nums)-1, -1, -1):
        nextDP = set()
        for t in dp:
            if(t + nums[i] == target):
                return True

            nextDP.add(t + nums[i])
            nextDP.add(t)
        dp = nextDP

    return True if target in dp else False

Explanation

  1. We initialize a set dp to store the subset sums.
  2. We add 0 to dp as an initial value.
  3. We calculate the target sum, which is half of the total sum of the array.
  4. We iterate through the array from right to left.
  5. For each element, we update dp with the sum of the current element and each element in dp.
  6. If we encounter a sum equal to the target, we return True.
  7. Finally, we check if the target sum exists in dp and return True or False accordingly.

Time Complexity: O(n * sum), where n is the number of elements in the array and sum is the total sum of the array.

Space Complexity: O(sum), where sum is the total sum of the array.

Dynamic Programming Result

Using Efficient Approach: Bitwise Manipulation

Another efficient approach employs bitwise manipulation to determine if partitioning is feasible. This method operates by constructing a bit mask representing possible subset sums. Let’s delve into the details.

Why it Works

  1. Bitmasking allows us to efficiently represent all possible sums of subsets using binary representations.
  2. By iterating through the array and updating the bitmask with bitwise OR operations, we efficiently build all possible subset sums.
  3. Checking if the desired subset sum exists becomes a simple bitwise operation, significantly reducing the time complexity compared to other approaches.
def canPartition(self, nums: List[int]) -> bool:
    total = sum(nums)
    if total & 1:
        return False

    subSetsum = total >> 1
    bitMask = 1
    for n in nums:
        bitMask = bitMask | bitMask << n

    return bitMask & 1 << subSetsum

Explanation:

  1. Total Calculation: The algorithm starts by computing the total sum of all elements in the input array nums. If the total sum is odd, it implies that the array cannot be partitioned into two subsets with equal sums. Hence, the algorithm returns False immediately.

  2. Target Subset Sum: Subsequently, the algorithm calculates the target subset sum, which is half of the total sum (total >> 1). This is because for partitioning to be possible, each subset should have a sum equal to half of the total sum.

  3. Bit Mask Construction:

    • The algorithm initializes a bit mask bitMask with a value of 1. Then, it iterates through each element n in the nums array.
    • For each element n, the algorithm updates the bit mask by performing a bitwise OR operation (|) with the bit mask left-shifted by n positions (bitMask << n). This operation effectively sets the bits corresponding to possible subset sums.
    • After iterating through all elements in nums, the bit mask represents the set of possible subset sums using bitwise manipulation.

  4. Subset Sum Existence Check:

    • Finally, the algorithm checks if the target subset sum exists in the constructed bit mask. It does this by performing a bitwise AND operation (&) between the bit mask and a left-shifted value representing the target subset sum (1 << subSetsum).
    • If the result of this bitwise AND operation is non-zero, it indicates that the target subset sum exists in the bit mask, and hence, partitioning is possible. The algorithm returns True in this case; otherwise, it returns False.

Time Complexity: O(n), where n is the length of the nums array.

Space Complexity: O(1), regardless of the size of the input array nums, it only stores a few integers for computation.

Bitwise Manipulation Result

Conclusion

In this guide, we explored various approaches to solve the Partition Equal Subset Sum problem. Starting from a brute force method to more efficient techniques like bit masking, we learned how to efficiently determine if it’s possible to partition an array into two subsets with equal sums.

Understanding these methods enhances your problem-solving skills and prepares you for tackling similar challenges in coding interviews and competitions.

Found this helpful? Follow me for more leetcode adventures! Questions? React out via email.

Next Articles in the Series