Partition Equal Subset Sum in DSA Python

Mental Model

We want to see if we can split a list of numbers into two groups with the same total. This means finding a subset that adds up to half the total sum.

Analogy: Imagine you have a pile of coins and want to divide them into two equal piles. You try picking some coins to make one pile exactly half the total value.

Numbers: [1, 5, 11, 5]
Total sum: 22
Target subset sum: 11
Subset search: [] -> trying to find sum 11

Dry Run Walkthrough

Input: list: [1, 5, 11, 5]

Goal: Find if we can split the list into two subsets with equal sum (11 each).

Step 1: Calculate total sum and target subset sum

Total sum = 22, Target subset sum = 11

Why: We need to find a subset that sums to half the total to partition equally

Step 2: Start with empty subset sum 0

Possible sums: {0}

Why: We begin with no numbers chosen, so sum 0 is possible

Step 3: Add number 1 to possible sums

Possible sums: {0, 1}

Why: By adding 1, we can now make sums 0 or 1

Step 4: Add number 5 to possible sums

Possible sums: {0, 1, 5, 6}

Why: Adding 5 extends sums by 5 more or combined with previous sums

Step 5: Add number 11 to possible sums

Possible sums so far: {0, 1, 5, 6}; 0 + 11 = 11 == target

Why: Hit target sum exactly when considering including 11 with empty previous sum

Step 6: Early return True

11 achievable → Partition possible: true

Why: Found subset summing to target during computation

Result:

Hit target during addition → Partition possible: true

Annotated Code

DSA Python

from typing import List

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        # If total is odd, can't split equally
        if total % 2 != 0:
            return False
        target = total // 2
        possible_sums = {0}
        for num in nums:
            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

# Driver code
nums = [1, 5, 11, 5]
sol = Solution()
print(sol.canPartition(nums))

if total % 2 != 0:

Check if total sum is odd -- odd sum means no equal partition

possible_sums = {0}

Start with sum 0 as possible (empty subset)

for num in nums:

Iterate over each number to update possible sums

for s in possible_sums:

Check all sums possible so far

if new_sum == target:

If we find subset sum equals target, return True immediately

possible_sums.update(new_sums)

Add new sums formed by including current number

return target in possible_sums

If after all numbers target sum is possible, return True

Output

True

Complexity Analysis

Time: O(n * target) because for each number we update possible sums up to half the total

Space: O(target) because we store possible sums up to half the total sum

vs Alternative: Naive approach tries all subsets (2^n), this uses dynamic programming to reduce to pseudo-polynomial time

Edge Cases

Empty list

Returns True because empty subsets trivially partition equally

DSA Python

if total % 2 != 0:

List with one element

Returns False because one element can't be split into two equal subsets

DSA Python

if total % 2 != 0:

List with all zeros

Returns True because zero sum subsets are equal

DSA Python

return target in possible_sums

When to Use This Pattern

When asked if a list can be split into two equal sum parts, reach for the subset sum dynamic programming pattern to find if half the total sum is achievable.

Common Mistakes

Mistake: Not checking if total sum is odd before processing
Fix: Add a check to return False immediately if total sum is odd

Mistake: Modifying the set of possible sums while iterating over it
Fix: Use a temporary set to collect new sums and update after iteration

Summary

Determines if a list can be split into two subsets with equal sum by finding a subset with sum equal to half the total.

Use when you need to check if equal partition of numbers is possible.

The key insight is to transform the problem into finding a subset sum equal to half the total sum.

Practice

1. What does the Partition Equal Subset Sum problem ask you to determine about a given list of positive integers?

easy

A. If the list contains any duplicate numbers

B. If the list can be split into two subsets with equal sums

C. If the list is sorted in ascending order

D. If the list contains only even numbers

Solution

1. Step 1: Understand the problem statement

   The problem asks if the input list can be divided into two parts where the sum of numbers in both parts is the same.

2. Step 2: Identify the key condition

   This means the total sum of the list must be even and there must be a subset with sum equal to half of the total sum.

3. Final Answer:

   If the list can be split into two subsets with equal sums -> Option B

4. Quick Check:

   Partition Equal Subset Sum = split into equal sum subsets [OK]

Hint: Check if total sum is even to start [OK]

Common Mistakes:

• Thinking it checks for duplicates
• Assuming list must be sorted
• Confusing with even number check

2. Which of the following Python code snippets correctly initializes a boolean list dp of size target + 1 with false values, except dp[0] set to true?

easy

A. dp = [True for _ in range(target + 1)]; dp[0] = True

B. dp = [True] * (target + 1); dp[0] = False

C. dp = [False for _ in range(target)]; dp[0] = True

D. dp = [False] * (target + 1); dp[0] = True

Solution

1. Step 1: Understand list initialization

   We want a list of size target+1 with all False except dp[0] = True.

2. Step 2: Check each option

   dp = [False] * (target + 1); dp[0] = True correctly creates a list of False of length target+1 and sets dp[0] to True.

3. Final Answer:

   dp = [False] * (target + 1); dp[0] = True -> Option D

4. Quick Check:

   Initialize dp with False, set dp[0] True [OK]

Hint: Use [False] * size and set dp[0] True manually [OK]

Common Mistakes:

• Using wrong list size (target instead of target+1)
• Setting dp[0] to False instead of True
• Using list comprehension with wrong range

3. What will be the output of the following Python code snippet?

nums = [1, 5, 11, 5]
total = sum(nums)
target = total // 2

dp = [False] * (target + 1)
dp[0] = True

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

print(dp[target])

medium

A. True

B. False

C. IndexError

D. SyntaxError

Solution

1. Step 1: Calculate total and target

   Total sum = 1+5+11+5 = 22, target = 11.

2. Step 2: Trace dp updates

   dp array tracks if sum j is possible. After processing all nums, dp[11] becomes True because subset [11] or [5,5,1] sums to 11.

3. Final Answer:

   True -> Option A

4. Quick Check:

   Subset sum 11 possible = True [OK]

Hint: Check if half sum subset exists using dp array [OK]

Common Mistakes:

• Forgetting to iterate backwards in inner loop
• Miscomputing total sum
• Confusing dp meaning (True means sum possible)

4. The following code attempts to solve the Partition Equal Subset Sum problem but has a bug. What is the bug?

def can_partition(nums):
    total = sum(nums)
    if total % 2 != 0:
        return False
    target = total // 2
    dp = [False] * target
    dp[0] = True
    for num in nums:
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]
    return dp[target]

medium

A. dp[0] should be False initially

B. The total sum check should be for odd numbers

C. dp list size should be target + 1, not target

D. The inner loop should iterate forwards, not backwards

Solution

1. Step 1: Check dp list size

   dp list is created with size target, but indices go up to target, so size must be target + 1.

2. Step 2: Identify impact of bug

   Accessing dp[target] causes IndexError because dp size is too small.

3. Final Answer:

   dp list size should be target + 1, not target -> Option C

4. Quick Check:

   dp size = target + 1 needed [OK]

Hint: dp size must cover index target inclusive [OK]

Common Mistakes:

• Using dp size = target causes index error
• Changing loop direction incorrectly
• Setting dp[0] to False breaks base case

5. Given the list nums = [2, 2, 3, 5], which of the following statements is true regarding the Partition Equal Subset Sum problem?

hard

A. It's not possible to partition into two subsets with equal sum

B. It's possible to partition into two subsets with equal sum: [2,2,3] and [5]

C. It's possible to partition into two subsets with equal sum: [2,3] and [2,5]

D. The problem requires subsets to have different sums

Solution

1. Step 1: Calculate total sum and target

   Total sum = 2+2+3+5 = 12, target = 6.

2. Step 2: Check possible subsets summing to 6

   Possible subsets: [2,2,2] no (only two 2s), [3,3] no (only one 3), [5,1] no 1 missing. No subset sums to 6 exactly.

3. Step 3: Verify partition

   Since no subset sums to 6, partition into equal sum subsets is not possible.

4. Final Answer:

   It's not possible to partition into two subsets with equal sum -> Option A

5. Quick Check:

   No subset sums to half total sum = no partition [OK]

Hint: Sum list, check if half sum subset exists [OK]

Common Mistakes:

• Assuming subsets like [2,3] and [2,5] sum equally
• Ignoring that subsets must sum exactly half
• Miscounting elements in subsets