Partition Equal Subset Sum in DSA C - Time & Space Complexity

Time Complexity: Partition Equal Subset Sum

O(n * sum)

Understanding Time Complexity

We want to know how the time needed to check if an array can be split into two equal sum parts grows as the array gets bigger.

How does the number of steps change when the array length or sum increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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];
    memset(dp, 0, sizeof(dp));
    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];
}
    

This code checks if the array can be split into two parts with equal sums using a dynamic programming approach.

Identify Repeating Operations

• Primary operation: Nested loops where the outer loop runs over each number and the inner loop runs over possible sums up to half the total sum.
• How many times: Outer loop runs n times (array length), inner loop runs up to sum/2 times.

How Execution Grows With Input

As the array size n or the sum sum grows, the number of operations grows roughly by multiplying these two.

Input Size (n)	Approx. Operations (sum/2)
10	10 * (sum/2)
100	100 * (sum/2)
1000	1000 * (sum/2)

Pattern observation: The time grows linearly with the number of elements and linearly with the half sum value.

Final Time Complexity

Time Complexity: O(n * sum)

This means the time needed grows proportionally with both the number of elements and the total sum of the array.

Common Mistake

[X] Wrong: "The time depends only on the number of elements, so it is O(n)."

[OK] Correct: The time also depends on the sum value because the inner loop runs up to half the sum, so ignoring sum underestimates the time.

Interview Connect

Understanding this time complexity helps you explain how dynamic programming solves subset problems efficiently compared to checking all subsets.

Self-Check

"What if we used recursion with memoization instead of this bottom-up approach? How would the time complexity change?"