Partition Equal Subset Sum in DSA Python - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Partition Equal Subset Sum Check

What is the output of the following code that checks if the list can be partitioned into two subsets with equal sum?

DSA Python

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

print(can_partition([1, 5, 11, 5]))

A True

B False

C SyntaxError

D TypeError

💡 Hint

Think about whether the total sum is even and if a subset sums to half the total.

The total sum is 22, which is even. The function uses dynamic programming to check if a subset sums to 11. Since [11] and [1,5,5] both sum to 11, the output is True.

❓ Predict Output

intermediate

Result of Partition Check on Odd Sum List

What does the function return when given a list with an odd total sum?

DSA Python

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

print(can_partition([1, 2, 3, 5]))

A True

B IndexError

C SyntaxError

D False

💡 Hint

Check the total sum and its parity before proceeding.

The total sum is 11, which is odd, so the function returns False immediately.

🧠 Conceptual

advanced

Understanding the Role of the DP Array

In the Partition Equal Subset Sum problem, what does the boolean dp array represent during the dynamic programming process?

A dp[i] counts how many subsets sum to i

B dp[i] is True if a subset of numbers sums exactly to i

C dp[i] stores the maximum sum less than or equal to i

D dp[i] is True if all numbers are less than i

💡 Hint

Think about what the algorithm needs to know to decide if partition is possible.

dp[i] being True means there exists a subset of the input list that sums exactly to i, which helps determine if half the total sum can be formed.

🔧 Debug

advanced

Identify the Error in Partition Code

What error will the following code produce when run?

DSA Python

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

print(can_partition([1, 2, 3, 4]))

A SyntaxError

B TypeError

C IndexError

D No error, outputs True

💡 Hint

Look carefully at the if statement syntax.

The if statement is missing a colon at the end, causing a SyntaxError.

🚀 Application

expert

Number of Items in DP Array for Large Input

If the input list sums to 1000, how many items does the dp array have in the Partition Equal Subset Sum dynamic programming solution?

A 1001

B 500

C 501

D 1000

💡 Hint

The dp array size depends on half the total sum plus one.

The dp array size is target + 1, where target = total // 2 = 500, so size is 501.

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