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

Time Complexity: Partition Equal Subset Sum

O(n * s)

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 size or sum increases?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function canPartition(nums: number[]): boolean {
  const total = nums.reduce((a, b) => a + b, 0);
  if (total % 2 !== 0) return false;
  const target = total / 2;
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;
  for (const num of nums) {
    for (let j = target; j >= num; j--) {
      dp[j] = dp[j] || dp[j - num];
    }
  }
  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

Identify the loops, recursion, array traversals that repeat.

• Primary operation: Nested loops where the outer loop goes through each number and the inner loop goes through possible sums up to half the total.
• How many times: Outer loop runs once per number (n times), inner loop runs up to target sum (s times).

How Execution Grows With Input

As the number of elements (n) or the target sum (s) grows, the steps increase roughly by multiplying these two.

Input Size (n)	Approx. Operations (n * s)
10 (sum ~ 50)	~ 10 * 25 = 250
100 (sum ~ 500)	~ 100 * 250 = 25,000
1000 (sum ~ 5000)	~ 1000 * 2500 = 2,500,000

Pattern observation: The steps grow roughly by multiplying the number of elements and half the total sum, so it grows faster if either increases.

Final Time Complexity

Time Complexity: O(n * s)

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

Common Mistake

[X] Wrong: "The time depends only on the number of elements (n)."

[OK] Correct: The sum value also affects how many steps the inner loop runs, so both n and the sum matter.

Interview Connect

Understanding this time complexity helps you explain how dynamic programming balances between input size and value range, a key skill in problem solving.

Self-Check

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