Partition Equal Subset Sum in DSA C - Build from Scratch

Partition Equal Subset Sum

📖 Scenario: You have a collection of items with weights represented as integers. You want to check if it is possible to split these items into two groups so that both groups have the same total weight.This is useful in real life when you want to pack two balanced boxes or divide tasks evenly.

🎯 Goal: Build a program that determines if the given list of integers can be partitioned into two subsets with equal sum.

📋 What You'll Learn

Create an integer array called nums with the exact values: 1, 5, 11, 5

Create an integer variable called total_sum to hold the sum of all elements in nums

Implement a function called canPartition that returns 1 if the array can be partitioned into two subsets with equal sum, otherwise 0

Print "YES" if partition is possible, else print "NO"

💡 Why This Matters

🌍 Real World

Balancing loads, dividing tasks or resources evenly, and packing problems often require checking if a set can be split into equal parts.

💼 Career

Understanding subset sum and partition problems is important in software engineering roles involving algorithms, optimization, and problem solving.

1

Create the array of numbers

Create an integer array called nums with the exact values 1, 5, 11, 5 and an integer variable n that stores the number of elements in nums.

DSA C

int nums[] = {1, 5, 11, 5};
int n = sizeof(nums) / sizeof(nums[0]);
// Your code here

Hint

Use sizeof(nums) / sizeof(nums[0]) to get the number of elements in the array.

2

Calculate the total sum of the array

Create an integer variable called total_sum and set it to 0. Then use a for loop with variable i from 0 to n - 1 to add each element of nums to total_sum.

DSA C

int nums[] = {1, 5, 11, 5};
int n = sizeof(nums) / sizeof(nums[0]);
int total_sum = 0;
// Your code here

Hint

Use a for loop to add each number in nums to total_sum.

3

Implement the partition check function

Write a function called canPartition that takes nums and n as parameters. Inside, if total_sum is odd, return 0. Otherwise, use a boolean array dp of size total_sum / 2 + 1 initialized to 0 except dp[0] set to 1. Use nested loops to update dp to check if a subset sum equal to total_sum / 2 is possible. Return dp[total_sum / 2].

DSA C

int nums[] = {1, 5, 11, 5};
int n = sizeof(nums) / sizeof(nums[0]);
int total_sum = 0;
for (int i = 0; i < n; i++) {
    total_sum += nums[i];
}

int canPartition(int* nums, int n) {
    // Your code here
}

Hint

Use dynamic programming with a boolean array to track possible subset sums.

4

Print the result

Use printf to print "YES" if canPartition(nums, n) returns 1, otherwise print "NO".

DSA C

int nums[] = {1, 5, 11, 5};
int n = sizeof(nums) / sizeof(nums[0]);
int total_sum = 0;
for (int i = 0; i = nums[i]; j--) {
            if (dp[j - nums[i]] == 1) {
                dp[j] = 1;
            }
        }
    }
    return dp[half];
}

// Your code here

Hint

Use printf("YES\n") or printf("NO\n") based on the function result.