Partition Equal Subset Sum in DSA Python - Execution Trace

Concept Flow - Partition Equal Subset Sum

Calculate total sum of array

↓

Check if total sum is odd?

Yes→Return False: cannot partition

No↓

Set target = total sum / 2

↓

Initialize DP array for subset sums

↓

For each number in array

↓

Update DP array to mark reachable sums

↓

Check if target sum is reachable

↓

Return True if reachable, else False

The flow calculates total sum, checks if partition is possible, then uses dynamic programming to find if a subset sums to half the total.

Execution Sample

DSA Python

nums = [1, 5, 11, 5]
total = sum(nums)
if total % 2 != 0:
    return False
target = total // 2
can_sum = [True] + [False]*target
for num in nums:
    for s in range(target, num-1, -1):
        can_sum[s] = can_sum[s] or can_sum[s-num]
return can_sum[target]

This code checks if the array can be split into two subsets with equal sum using a bottom-up DP approach.

Execution Table

Step	Operation	Current Number	DP Array State	Explanation
1	Calculate total sum	-	-	Sum of [1,5,11,5] is 22
2	Check if total sum is odd	22	-	22 is even, continue
3	Set target	22	-	Target sum is 11
4	Initialize DP array	-	[True, False, False, False, False, False, False, False, False, False, False, False]	Only sum 0 is reachable initially
5	Process number 1	1	[True, True, False, False, False, False, False, False, False, False, False, False]	Sum 1 reachable by including 1
6	Process number 5	5	[True, True, False, False, False, True, True, False, False, False, False, False]	Sums 5 and 6 reachable
7	Process number 11	11	[True, True, False, False, False, True, True, False, False, False, False, True]	Sum 11 reachable by including 11
8	Process number 5	5	[True, True, False, False, False, True, True, False, False, False, True, True]	Additional sums reachable including 5
9	Check if target sum reachable	-	-	DP[target] is True, partition possible
10	Return result	-	-	Return True

💡 DP array shows target sum 11 is reachable, so partition is possible

Variable Tracker

Variable	Start	After Step 5	After Step 6	After Step 7	After Step 8	Final
total	0	22	22	22	22	22
target	0	11	11	11	11	11
can_sum	[True, False, ..., False]	[True, True, False, False, False, False, False, False, False, False, False, False]	[True, True, False, False, False, True, True, False, False, False, False, False]	[True, True, False, False, False, True, True, False, False, False, False, True]	[True, True, False, False, False, True, True, False, False, False, True, True]	[True, True, False, False, False, True, True, False, False, False, True, True]
num	-	1	5	11	5	-

Key Moments - 3 Insights

Why do we check if the total sum is odd before proceeding?

Because if the total sum is odd (see Step 2 in execution_table), it's impossible to split the array into two equal parts, so we return False immediately.

Why do we update the DP array backwards from target to num?

Updating backwards (Step 5-8) prevents using the same number multiple times in one iteration, ensuring each number is only counted once per subset.

What does the DP array represent at each step?

The DP array shows which sums are reachable with the numbers processed so far (see DP Array State in execution_table). True means that sum is achievable.

Visual Quiz - 3 Questions

Look at the execution_table at Step 5, what sums are reachable after processing number 1?

A Only sum 0

B Sums 1 and 5

C Sums 0 and 1

D All sums up to 11

💡 Hint

Check the DP Array State column at Step 5 in execution_table

At which step does the DP array first show that the target sum 11 is reachable?

A Step 6

B Step 7

C Step 8

D Step 9

💡 Hint

Look for True at index 11 in DP Array State column in execution_table

If the total sum was 23 instead of 22, what would happen at Step 2?

A Return False immediately

B Continue to DP calculation

C Return True immediately

D Set target to 11

💡 Hint

Refer to the Check if total sum is odd step in execution_table

Concept Snapshot

Partition Equal Subset Sum:
- Calculate total sum of array
- If sum is odd, return False
- Set target = sum / 2
- Use DP array to track reachable sums
- Update DP for each number backwards
- If target sum reachable, return True
- Else, return False

Full Transcript

The Partition Equal Subset Sum problem checks if an array can be split into two subsets with equal sums. First, we sum all numbers. If the sum is odd, partitioning is impossible. If even, we set the target as half the sum. We create a DP array where each index represents if that sum is reachable. Initially, only sum 0 is reachable. For each number, we update the DP array backwards to mark new reachable sums. After processing all numbers, if the target sum is reachable, we return True, else False. This approach uses dynamic programming to efficiently solve the problem.

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