Partition Equal Subset Sum in DSA C#

Mental Model

We want to split a list of numbers into two groups with the same total sum. If we can find one group that sums to half the total, the other group automatically matches.

Analogy: Imagine you have a pile of coins and want to divide them into two equal piles. If you can pick some coins that add up to half the total money, the rest will be the other half.

List: [1, 5, 11, 5]
Total sum = 22
Target sum = 11
Try to find subset -> [5, 5, 1] = 11
Remaining subset -> [11] = 11

Dry Run Walkthrough

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

Goal: Find if we can split the list into two subsets with equal sum

Step 1: Calculate total sum and check if it's even

List: [1, 5, 11, 5]
Total sum = 22 (even)
Target sum = 11

Why: If total sum is odd, equal partition is impossible

Step 2: Start checking subsets to find sum 11 using dynamic programming

DP array initialized for sum 0 to 11
Initially dp[0] = true (empty subset)

Why: We track which sums are possible with subsets

Step 3: Include 1: update dp for sums achievable with 1

dp[0] = true, dp[1] = true (using 1)

Why: We can make sum 1 by including 1

Step 4: Include 5: update dp for sums achievable with 1 and 5

dp[0] = true, dp[1] = true, dp[5] = true, dp[6] = true (1+5)

Why: We can make sums 5 and 6 by adding 5 to previous sums

Step 5: Include 11: update dp for sums achievable with 1,5,11

dp[11] = true (directly from 11), dp[6], dp[5], dp[1], dp[0] remain true

Why: We can make sum 11 by including 11 alone

Step 6: Include last 5: update dp for sums achievable with all numbers

dp[10] = true (5+5), dp[11] = true, dp[16] not needed (target 11)

Why: We can make sum 10 and 11, confirming target sum is achievable

Result:

dp[11] = true means subset with sum 11 exists
Answer: true (partition possible)

Annotated Code

DSA C#

using System;

class PartitionEqualSubsetSum {
    public static bool CanPartition(int[] nums) {
        int totalSum = 0;
        foreach (int num in nums) {
            totalSum += num;
        }
        if (totalSum % 2 != 0) return false; // odd sum can't split equally

        int target = totalSum / 2;
        bool[] dp = new bool[target + 1];
        dp[0] = true; // zero sum is always possible

        foreach (int num in nums) {
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num]; // update dp for current num
            }
        }

        return dp[target];
    }

    static void Main() {
        int[] nums = {1, 5, 11, 5};
        bool result = CanPartition(nums);
        Console.WriteLine(result);
    }
}

if (totalSum % 2 != 0) return false; // odd sum can't split equally

Check if total sum is even; if not, partition impossible

dp[0] = true; // zero sum is always possible

Initialize dp to mark sum zero achievable without elements

for (int j = target; j >= num; j--) { dp[j] = dp[j] || dp[j - num]; // update dp for current num }

Update dp array to reflect sums achievable including current number

return dp[target];

Return if target sum subset exists

Output

True

Complexity Analysis

Time: O(n * sum) because we check each number against all sums up to half the total

Space: O(sum) because we use a one-dimensional array to store achievable sums

vs Alternative: Naive approach tries all subsets with exponential time; DP reduces it to polynomial time

Edge Cases

Empty list

Returns false because no subsets exist

DSA C#

if (totalSum % 2 != 0) return false;

List with one element

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

DSA C#

if (totalSum % 2 != 0) return false;

All elements zero

Returns true because two subsets with sum zero are possible

DSA C#

dp[0] = true;

When to Use This Pattern

When asked if a list can be split into two equal sum parts, use the Partition Equal Subset Sum pattern because it transforms the problem into a subset sum check for half the total.

Common Mistakes

Mistake: Not checking if total sum is even before proceeding
Fix: Add a check to return false immediately if total sum is odd

Mistake: Updating dp array from start to end causing reuse of updated values in the same iteration
Fix: Update dp array from end to start to avoid counting the same number multiple times

Summary

Determines if a list can be split into two subsets with equal sum.

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

The key insight is to find a subset with sum equal to half the total sum.

Practice

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

easy

A. If the array is sorted in ascending order

B. If the array contains any duplicate elements

C. If the array contains only positive numbers

D. If the array can be split into two subsets with equal sums

Solution

1. Step 1: Understand the problem statement

   The problem asks whether the array can be divided into two parts where the sum of elements in both parts is the same.

2. Step 2: Clarify what is being checked

   It is not about duplicates, sorting, or positivity, but about equal sum partitioning.

3. Final Answer:

   If the array can be split into two subsets with equal sums -> Option D

4. Quick Check:

   Partition Equal Subset Sum = Split array into two equal sum subsets [OK]

Hint: Focus on splitting array into two equal sum parts [OK]

Common Mistakes:

• Confusing with checking duplicates
• Thinking about sorting order
• Assuming all numbers must be positive

2. Which of the following C# code snippets correctly initializes a boolean array named dp of size sum + 1 for the Partition Equal Subset Sum problem?

easy

A. bool[] dp = new bool[sum];

B. bool[] dp = new bool(sum + 1);

C. bool[] dp = new bool[sum + 1];

D. bool dp = new bool[sum + 1];

Solution

1. Step 1: Understand array initialization syntax in C#

   Arrays are initialized with square brackets and the size inside new[]. For size sum+1, use new bool[sum + 1].

2. Step 2: Check each option

   bool[] dp = new bool[sum]; misses +1, bool dp = new bool[sum + 1]; uses wrong type declaration, bool[] dp = new bool(sum + 1); uses parentheses which is invalid.

3. Final Answer:

   bool[] dp = new bool[sum + 1]; -> Option C

4. Quick Check:

   Correct C# array syntax = bool[] dp = new bool[sum + 1]; [OK]

Hint: Use square brackets and new keyword for arrays in C# [OK]

Common Mistakes:

• Forgetting +1 for array size
• Using parentheses instead of square brackets
• Declaring array as single bool variable

3. What will be the output of the following C# code snippet for the input array nums = new int[] {1, 5, 11, 5};?

bool CanPartition(int[] nums) {
    int sum = 0;
    foreach (int num in nums) sum += num;
    if (sum % 2 != 0) return false;
    int target = sum / 2;
    bool[] dp = new bool[target + 1];
    dp[0] = true;
    foreach (int num in nums) {
        for (int i = target; i >= num; i--) {
            dp[i] = dp[i] || dp[i - num];
        }
    }
    return dp[target];
}

Console.WriteLine(CanPartition(nums));

medium

A. true

B. false

C. Compile-time error

D. Runtime exception

Solution

1. Step 1: Calculate total sum and check parity

   Sum = 1+5+11+5 = 22, which is even, so continue.

2. Step 2: Use dynamic programming to check subset sum

   Target = 11. The dp array tracks if sum i is achievable. The code finds that subset {11} or {5,5,1} sums to 11, so dp[11] = true.

3. Final Answer:

   true -> Option A

4. Quick Check:

   Sum even and subset sum found = true [OK]

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

Common Mistakes:

• Not checking if sum is even
• Incorrect dp array update direction
• Returning false prematurely

4. Identify the bug in the following C# code snippet for Partition Equal Subset Sum and select the correct fix:

bool CanPartition(int[] nums) {
    int sum = 0;
    foreach (int num in nums) sum += num;
    if (sum % 2 != 0) return false;
    int target = sum / 2;
    bool[] dp = new bool[target];
    dp[0] = true;
    foreach (int num in nums) {
        for (int i = target; i >= num; i--) {
            dp[i] = dp[i] || dp[i - num];
        }
    }
    return dp[target];
}

medium

A. Initialize dp array with false values explicitly

B. Change dp array size to target + 1

C. Change loop to iterate from 0 to target

D. Remove the dp[0] = true assignment

Solution

1. Step 1: Check dp array size and indexing

   dp array is declared with size target, but dp[target] is accessed, causing out-of-range error.

2. Step 2: Fix array size to include target index

   Change dp size to target + 1 to safely access dp[target].

3. Final Answer:

   Change dp array size to target + 1 -> Option B

4. Quick Check:

   Array size must cover all indices used [OK]

Hint: Array size must be one more than max index accessed [OK]

Common Mistakes:

• Ignoring array index out of range
• Changing loop direction unnecessarily
• Removing dp[0] initialization

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

hard

A. The array cannot be partitioned into two subsets with equal sum

B. The array can be partitioned into two subsets with equal sum: {2,3} and {2,5}

C. The array can be partitioned into two subsets with equal sum: {2,2,3} and {5}

D. The array can be partitioned into two subsets with equal sum: {3,5} and {2,2}

Solution

1. Step 1: Calculate total sum of array elements

   Sum = 2 + 2 + 3 + 5 = 12, which is even, so partition might be possible.

2. Step 2: Check possible subsets for half sum (6)

   Half sum = 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 given options

   The array can be partitioned into two subsets with equal sum: {2,3} and {2,5} sums: {2,3}=5 and {2,5}=7 (not equal). The array can be partitioned into two subsets with equal sum: {2,2,3} and {5} sums: {2,2,3}=7 and {5}=5 (not equal). The array can be partitioned into two subsets with equal sum: {3,5} and {2,2} sums: {3,5}=8 and {2,2}=4 (not equal).

4. Final Answer:

   The array cannot be partitioned into two subsets with equal sum -> Option A

5. Quick Check:

   Sum even but no subset sums to half sum = false [OK]

Hint: Check if any subset sums exactly to half total sum [OK]

Common Mistakes:

• Assuming even sum means partition always possible
• Incorrectly summing subsets
• Ignoring subset element counts