Equal Partition (Partition Equal Subset Sum)

▶

Steps

setup

Calculate total sum and check parity

Calculate the total sum of the array [1,5,11,5], which is 22. Since 22 is even, proceed to find a subset with sum 11.

💡 Checking if the total sum is even is crucial because if it's odd, equal partition is impossible.

Line:

total = sum(nums)
if total % 2 != 0:
    return False

💡 The problem reduces to finding a subset with sum equal to half the total sum.

setup

Initialize dp array with dp[0] = True

Create a dp array of length target+1 (12), initialized with False except dp[0] which is True, representing that sum 0 is always achievable.

💡 dp[0] = True because an empty subset always sums to zero.

Line:

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

💡 This initialization sets the base case for the dynamic programming approach.

fill_cells

Start processing first number: 1

Begin processing the first number 1. We will update dp array for sums from target down to 1.

💡 Processing each number updates achievable sums in dp array.

Line:

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

💡 We check if sum w can be formed either previously or by adding current number 1 to a previously achievable sum w-1.

fill_cells

Update dp for w=11 with number 1

Check if sum 11 can be achieved by including number 1: dp[11] = dp[11] or dp[10]. Both are False, so dp[11] remains False.

💡 At w=11, no new sum achievable by adding 1.

Line:

dp[11] = dp[11] or dp[11 - 1]

💡 No change at dp[11] since dp[10] is False.

fill_cells

Update dp for w=1 with number 1

Check if sum 1 can be achieved by including number 1: dp[1] = dp[1] or dp[0]. dp[0] is True, so dp[1] becomes True.

💡 Sum 1 is now achievable by including number 1.

Line:

dp[1] = dp[1] or dp[1 - 1]

💡 dp[1] updated to True, reflecting achievable sum.

fill_cells

Process second number: 5, start with w=11

Process number 5. For w=11, update dp[11] = dp[11] or dp[6]. dp[6] is False, so dp[11] remains True from previous step.

💡 Check if sum 11 achievable by adding 5 to sum 6.

Line:

dp[11] = dp[11] or dp[11 - 5]

💡 No change at dp[11] since dp[6] is False.

fill_cells

Update dp for w=6 with number 5

Check if sum 6 can be achieved by including number 5: dp[6] = dp[6] or dp[1]. dp[1] is True, so dp[6] becomes True.

💡 Sum 6 is now achievable by adding 5 to sum 1.

Line:

dp[6] = dp[6] or dp[6 - 5]

💡 dp[6] updated to True.

fill_cells

Update dp for w=5 with number 5

Check if sum 5 can be achieved by including number 5: dp[5] = dp[5] or dp[0]. dp[0] is True, so dp[5] becomes True.

💡 Sum 5 is now achievable by including number 5 alone.

Line:

dp[5] = dp[5] or dp[5 - 5]

💡 dp[5] updated to True.

fill_cells

Process third number: 11 (w=11 only)

Process number 11. Only w=11 is valid for update: dp[11] = dp[11] or dp[0]. Since dp[0] is True, dp[11] remains True.

💡 Including 11 allows achieving sum 11 directly.

Line:

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

💡 This step shows how a large number can directly achieve the target sum.

fill_cells

Process fourth number: 5, start with w=11

Process last number 5. For w=11, update dp[11] = dp[11] or dp[6]. dp[6] is True, so dp[11] remains True.

💡 Check if sum 11 achievable by adding 5 to sum 6.

Line:

dp[11] = dp[11] or dp[11 - 5]

💡 dp[11] remains True.

fill_cells

Update dp for w=10 with number 5

Check if sum 10 can be achieved by including number 5: dp[10] = dp[10] or dp[5]. dp[5] is True, so dp[10] becomes True.

💡 Sum 10 is now achievable by adding 5 to sum 5.

Line:

dp[10] = dp[10] or dp[10 - 5]

💡 dp[10] updated to True.

fill_cells

Update dp for w=5 with number 5

Check if sum 5 can be achieved by including number 5: dp[5] = dp[5] or dp[0]. dp[0] is True, so dp[5] remains True.

💡 Sum 5 remains achievable.

Line:

dp[5] = dp[5] or dp[5 - 5]

💡 No change at dp[5].

traverse

Check final answer at dp[target]

Check dp[11], which is True, indicating a subset with sum 11 exists, so the array can be partitioned equally.

💡 The final dp cell tells if the target sum is achievable.

Line:

return dp[target]

💡 The problem reduces to checking dp[target] after processing all numbers.

def canPartition(nums):
    total = sum(nums)  # STEP 1
    if total % 2 != 0:  # STEP 1
        return False
    target = total // 2  # STEP 2
    dp = [False] * (target + 1)  # STEP 2
    dp[0] = True  # STEP 2

    for i, num in enumerate(nums):  # STEP 3-12
        for w in range(target, num - 1, -1):
            dp[w] = dp[w] or dp[w - num]

    return dp[target]  # STEP 13

if __name__ == '__main__':
    print(canPartition([1,5,11,5]))  # True
    print(canPartition([1,2,3,5]))   # False

📊

Equal Partition (Partition Equal Subset Sum) - Watch the Algorithm Execute, Step by Step

Watching the dp array update step-by-step reveals how the problem reduces to a subset sum problem and how the algorithm efficiently tracks achievable sums.

Initializing dp array

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	?	?	?	?	?	?	?	?	?	?	?	?

Initializing dp array

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	True	False	False	False	False	False	False	False	False	False	False	False

dp[0] = True

Item 0 - wt:1 val:1

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	True	False	False	False	False	False	False	False	False	False	False	False

Item 0 - wt:1 val:1

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	True	False	False	False	False	False	False	False	False	False	False	False

No update

Item 0 - wt:1 val:1

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	True	True	False	False	False	False	False	False	False	False	False	False

dp[1] updated

Item 1 - wt:5 val:5

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	True	True	False	False	False	False	False	False	False	False	False	True

dp[11] remains True

Item 1 - wt:5 val:5

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	True	True	False	False	False	False	True	False	False	False	False	True

dp[6] updated

Item 1 - wt:5 val:5

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	True	True	False	False	False	True	True	False	False	False	False	True

dp[5] updated

Item 2 - wt:11 val:11

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	True	True	False	False	False	True	True	False	False	False	False	True

dp[11] updated True

Item 3 - wt:5 val:5

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	True	True	False	False	False	True	True	False	False	False	False	True

dp[11] remains True

Item 3 - wt:5 val:5

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	True	True	False	False	False	True	True	False	False	False	True	True

dp[10] updated

Item 3 - wt:5 val:5

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	True	True	False	False	False	True	True	False	False	False	True	True

dp[5] remains True

Initializing dp array

i\w	0	1	2	3	4	5	6	7	8	9	10	11
i=0	True	True	False	False	False	True	True	False	False	False	True	True

Answer: True

Key Takeaways

✓ The problem reduces to checking if a subset sum equal to half the total sum exists.

This insight is hard to see from code alone because the reduction is conceptual, but the visualization shows the target sum clearly.

✓ The dp array tracks achievable sums and updates monotonically as numbers are processed.

Seeing the dp array update step-by-step reveals how sums accumulate and why backward iteration is necessary.

✓ The final answer is simply dp[target], showing if the target sum is achievable after processing all numbers.

This clarifies that the complex problem is solved by a simple boolean check at the end.

Practice

1. The following code attempts to implement the space-optimized 0/1 Knapsack solution. Identify the line that contains a subtle bug that can cause incorrect results.

def knapsack_space_optimized(weights, values, W):
    n = len(weights)
    dp = [0] * (W + 1)
    for i in range(n):
        for w in range(weights[i], W + 1):  # Note: iterating forwards
            dp[w] = max(dp[w], dp[w - weights[i]] + values[i])
    return dp[W]

medium

A. Line 5: Inner loop iterating forwards over weights.

B. Line 4: Outer loop iterating over items.

C. Line 2: Initializing dp array with zeros.

D. Line 6: Updating dp[w] with max of current and new value.

Solution

1. Step 1: Analyze iteration order in inner loop

   The inner loop iterates forwards from weights[i] to W, which causes the current item to be counted multiple times in the same iteration, violating 0/1 knapsack constraints.

2. Step 2: Correct iteration direction

   Iterating backwards (from W down to weights[i]) ensures each item is only counted once per capacity, preserving correctness.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Forward iteration causes overcounting items [OK]

Hint: Inner loop must iterate backwards to avoid overcounting [OK]

Common Mistakes:

• Iterating forwards in dp array updates for 0/1 knapsack.

2. What is the time complexity of the space-optimized bottom-up dynamic programming solution for the coin change minimum coins problem, given n coins and amount S?

medium

A. O(n * S) because for each amount up to S, all n coins are checked

B. O(n^S) due to exploring all combinations recursively

C. O(S^2) since the dp array is updated for each sub-amount multiple times

D. O(n + S) as the algorithm iterates once over coins and once over amounts

Solution

1. Step 1: Identify loops in the bottom-up DP

   Outer loop runs from 1 to S (amount), inner loop runs over n coins.

2. Step 2: Calculate total operations

   Each dp[i] is updated by checking all n coins, so total operations = n * S.

3. Final Answer:

   Option A -> Option A

4. Quick Check:

   Nested loops over amount and coins -> O(n * S) [OK]

Hint: Nested loops over amount and coins yield O(n*S) [OK]

Common Mistakes:

• Confusing recursion exponential time with DP
• Assuming quadratic due to dp updates

3. Suppose the problem changes so that you can use each item an unlimited number of times (unbounded knapsack). Which modification to the space-optimized bottom-up DP code correctly solves this variant?

hard

A. Change the inner loop to iterate forwards from weights[i] up to W.

B. Add memoization to the recursive solution to avoid recomputation.

C. Change the inner loop to iterate backwards from W down to weights[i].

D. Use a greedy approach selecting items with the highest value-to-weight ratio repeatedly.

Solution

1. Step 1: Understand difference between 0/1 and unbounded knapsack

   In unbounded knapsack, items can be chosen multiple times, so dp[w] can be updated using dp[w - weights[i]] from the same iteration.

2. Step 2: Identify correct iteration order

   Iterating forwards from weights[i] to W allows reuse of updated dp values within the same iteration, enabling multiple counts of the same item.

3. Step 3: Why other options fail

   Backward iteration prevents multiple usage in one iteration (wrong for unbounded). Memoization helps but is not the direct fix. Greedy fails for 0/1 and unbounded knapsack except fractional case.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Forward iteration enables unlimited item reuse [OK]

Hint: Unbounded knapsack requires forward iteration in dp updates [OK]

Common Mistakes:

• Using backward iteration from 0/1 knapsack causes incorrect results.

4. Suppose the problem is modified so that each element in the array can be used multiple times (unlimited reuse) to form k equal sum subsets. Which of the following modifications to the DP with bitmask tabulation approach correctly adapts to this change?

hard

A. Use backtracking with memoization on subsets but do not use bitmasking since reuse breaks subset uniqueness

B. Keep the same bitmask DP but allow setting dp[next_mask] multiple times without restriction

C. Replace bitmask DP with a classic unbounded knapsack DP that tracks sums without bitmasking

D. Modify the bitmask DP to reset dp states after each full subset sum is reached to allow reuse

Solution

1. Step 1: Understand reuse impact

   Allowing unlimited reuse breaks the uniqueness assumption of subsets represented by bitmasks.

2. Step 2: Identify suitable DP approach

   Classic unbounded knapsack DP tracks sums without bitmasking, correctly handling reuse.

3. Step 3: Evaluate other options

   Bitmask DP relies on unique element usage; modifying it without removing bitmasking leads to incorrect states.

4. Final Answer:

   Option C -> Option C

5. Quick Check:

   Unbounded knapsack DP handles reuse correctly [OK]

Hint: Bitmask DP assumes unique usage; reuse needs unbounded knapsack DP [OK]

Common Mistakes:

• Trying to reuse bitmask DP without removing uniqueness assumption
• Ignoring that reuse breaks subset partitioning logic

5. Suppose the subset sum problem is modified so that each number can be chosen multiple times (unbounded). Which modification to the space-optimized DP code correctly solves this variant?

hard

A. Change the inner loop to iterate forwards from num to S, allowing reuse of the same number multiple times.

B. Keep the inner loop iterating backwards from S to num, as in the 0/1 subset sum problem.

C. Use a recursive brute force approach without memoization to handle multiple uses.

D. Sort the input array and apply a greedy approach picking largest numbers first.

Solution

1. Step 1: Understand difference between 0/1 and unbounded knapsack

   In unbounded knapsack, items can be reused multiple times, so dp updates must allow reuse within the same iteration.

2. Step 2: Modify iteration direction

   Iterating forwards allows dp[w] to use dp[w - num] updated in the same iteration, enabling multiple uses of num.

3. Step 3: Confirm correctness

   Backward iteration prevents reuse in the same iteration, which is incorrect for unbounded variant.

4. Final Answer:

   Option A -> Option A

5. Quick Check:

   Forward iteration enables multiple uses -> correct for unbounded knapsack [OK]

Hint: Unbounded knapsack requires forward iteration to allow reuse [OK]

Common Mistakes:

• Using backward iteration from 0/1 knapsack
• Trying greedy or brute force without memoization