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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of subset sum check for equal partition

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

DSA C

#include <stdio.h>
#include <stdbool.h>

bool canPartition(int* nums, int numsSize) {
    int sum = 0;
    for (int i = 0; i < numsSize; i++) {
        sum += nums[i];
    }
    if (sum % 2 != 0) return false;
    int target = sum / 2;
    bool dp[target + 1];
    for (int i = 0; i <= target; i++) dp[i] = false;
    dp[0] = true;
    for (int i = 0; i < numsSize; i++) {
        for (int j = target; j >= nums[i]; j--) {
            dp[j] = dp[j] || dp[j - nums[i]];
        }
    }
    return dp[target];
}

int main() {
    int nums[] = {1, 5, 11, 5};
    int size = sizeof(nums) / sizeof(nums[0]);
    if (canPartition(nums, size))
        printf("true\n");
    else
        printf("false\n");
    return 0;
}

A Compilation error

B false

C Runtime error

D true

💡 Hint

Check if the total sum is even and then use dynamic programming to find subset with sum equal to half.

The array sums to 22, which is even. The subset {11, 5} sums to 16, but the correct subset is {11, 5} and {1, 5, 5} both sum to 11. The code correctly identifies this and returns true.

🧠 Conceptual

intermediate

Why must the total sum be even for partition?

Why is it necessary for the total sum of the array elements to be even to partition it into two subsets with equal sum?

A Because two equal integers must sum to an even number

B Because odd sums can be split into two equal parts

C Because the array length must be even

D Because the subsets must have the same number of elements

💡 Hint

Think about what happens if the sum is odd and you try to split it equally.

Two equal integers sum to an even number. If the total sum is odd, it cannot be split into two equal integer sums.

🔧 Debug

advanced

Identify the error in subset sum implementation

What error does the following code produce when trying to check partition equal subset sum?

DSA C

#include <stdio.h>
#include <stdbool.h>

bool canPartition(int* nums, int numsSize) {
    int sum = 0;
    for (int i = 0; i < numsSize; i++) {
        sum += nums[i];
    }
    if (sum % 2 != 0) return false;
    int target = sum / 2;
    bool dp[target + 1];
    for (int i = 0; i < target; i++) dp[i] = false;
    dp[0] = true;
    for (int i = 0; i < numsSize; i++) {
        for (int j = target; j >= nums[i]; j--) {
            dp[j] = dp[j] || dp[j - nums[i]];
        }
    }
    return dp[target];
}

int main() {
    int nums[] = {1, 2, 3, 5};
    int size = sizeof(nums) / sizeof(nums[0]);
    if (canPartition(nums, size))
        printf("true\n");
    else
        printf("false\n");
    return 0;
}

A Sum calculation is incorrect

B Loop indices are out of bounds causing segmentation fault

C dp array initialization misses last element, causing undefined behavior

D No error, code runs correctly

💡 Hint

Check the loop that initializes the dp array.

The dp array is of size target+1 but the loop initializes only up to target-1, leaving dp[target] uninitialized which can cause wrong results or undefined behavior.

🚀 Application

advanced

Minimum subset sum difference using partition logic

Given an array, which approach helps find the minimum difference between sums of two subsets?

A Use partition equal subset sum logic to find all achievable sums up to half total and pick closest to half

B Sort array and split into two halves directly

C Sum all elements and divide by length

D Use greedy approach to assign elements alternately to subsets

💡 Hint

Think about how subset sums relate to partitioning.

By finding all subset sums up to half the total sum, we can find the subset sum closest to half, minimizing the difference between two subsets.

❓ Predict Output

expert

Output of partition check with negative numbers

What is the output of this code that attempts to check partition equal subset sum with negative numbers included?

DSA C

#include <stdio.h>
#include <stdbool.h>

bool canPartition(int* nums, int numsSize) {
    int sum = 0;
    for (int i = 0; i < numsSize; i++) {
        sum += nums[i];
    }
    if (sum % 2 != 0) return false;
    int target = sum / 2;
    bool dp[target + 1];
    for (int i = 0; i <= target; i++) dp[i] = false;
    dp[0] = true;
    for (int i = 0; i < numsSize; i++) {
        for (int j = target; j >= nums[i]; j--) {
            dp[j] = dp[j] || dp[j - nums[i]];
        }
    }
    return dp[target];
}

int main() {
    int nums[] = {1, 2, -1, 4};
    int size = sizeof(nums) / sizeof(nums[0]);
    if (canPartition(nums, size))
        printf("true\n");
    else
        printf("false\n");
    return 0;
}

A false

B Runtime error due to negative index in dp array

C Compilation error

D true

💡 Hint

Consider how negative numbers affect array indexing.

The code uses dp[j - nums[i]] where nums[i] can be negative, causing negative index access which leads to runtime error.