Partition Equal Subset Sum in DSA C# - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Partition Equal Subset Sum Check

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

DSA C#

using System;

class Program {
    static 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 j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        return dp[target];
    }

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

A Compilation error

B Runtime exception

C False

D True

💡 Hint

Check if the total sum is even and if a subset sums to half the total.

The total sum is 22, which is even. Half is 11, and subsets {1,5,5} and {11} both sum to 11. The code correctly finds a subset with sum 11, so output is True.

🧠 Conceptual

intermediate

Understanding the Partition Equal Subset Sum Problem

Which statement best describes the Partition Equal Subset Sum problem?

A Find if the array can be split into two subsets with equal sums.

B Find the maximum sum subset in the array.

C Find the minimum number of subsets to cover all elements.

D Find if the array contains duplicate elements.

💡 Hint

Think about dividing the array into two parts with the same total.

The problem asks if the array can be divided into two subsets where the sum of elements in both subsets is equal.

🔧 Debug

advanced

Identify the Error in Subset Sum Implementation

What error will the following code produce when checking partition equal subset sum?

DSA C#

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 j = target; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }
    return dp[target];
}

A Compilation error

B No error, works correctly

C IndexOutOfRangeException

D Returns incorrect result

💡 Hint

Check the size of the dp array and the indices accessed.

The dp array is created with size target, but indices go up to target, causing IndexOutOfRangeException.

🚀 Application

advanced

Result of Partition Check on Specific Input

Given the input array [2, 2, 3, 5], what will the Partition Equal Subset Sum function return?

DSA C#

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 j = target; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }
    return dp[target];
}

// Input: [2, 2, 3, 5]

A Compilation error

B False

C Runtime error

D True

💡 Hint

Calculate the total sum and check if half sum subset exists.

Sum is 12, half is 6. Possible subsets sums: 2,4,5,7,8,10 but no subset sums exactly to 6. So returns False.

❓ Predict Output

expert

Output of Partition Equal Subset Sum with Negative Numbers

What is the output of the following code when the input array contains negative numbers?

DSA C#

using System;

class Program {
    static 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 j = target; j >= num && j >= 0; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        return dp[target];
    }

    static void Main() {
        int[] nums = {1, -1, 2, 4};
        Console.WriteLine(CanPartition(nums));
    }
}

A Runtime exception

B False

C True

D Compilation error

💡 Hint

Consider how negative numbers affect array indexing.

Negative numbers cause invalid indices in dp array access (j - num) leading to runtime exception.

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