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

Time Complexity: Partition Equal Subset Sum

O(n * sum)

Understanding Time Complexity

We want to understand how the time needed to check if an array can be split into two equal sum parts grows as the array size or values grow.

How does the algorithm's work increase when the input changes?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

function canPartition(nums) {
  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 half the total sum (target) times for each number.

How Execution Grows With Input

The work grows with both the number of elements and the half of the total sum of elements.

Input Size (n)	Approx. Operations
10 (sum ~100)	10 * 50 = 500
100 (sum ~1000)	100 * 500 = 50,000
1000 (sum ~10,000)	1000 * 5000 = 5,000,000

Pattern observation: The operations grow roughly by multiplying the number of elements by the half sum, so doubling input size or sum roughly doubles the work.

Final Time Complexity

Time Complexity: O(n * sum)

This means the time needed grows 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 total sum value because the algorithm checks sums up to half the total, so larger sums increase the work.

Interview Connect

Understanding this time complexity helps you explain how dynamic programming balances between input size and value range, a key skill for solving subset and partition problems.

Self-Check

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

Practice

1. What does the Partition Equal Subset Sum problem ask you to find in a given array of positive integers?

easy

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

B. The maximum sum of any subset in the array

C. The minimum number of subsets needed to cover all elements

D. The sum of all elements in the array

Solution

1. Step 1: Understand the problem goal

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

2. Step 2: Compare options with problem definition

   Only Whether the array can be split into two subsets with equal sums matches this goal exactly. Other options describe different problems.

3. Final Answer:

   Whether the array can be split into two subsets with equal sums -> Option A

4. Quick Check:

   Partition Equal Subset Sum = split into equal sum subsets [OK]

Hint: Look for splitting array into two equal sum parts [OK]

Common Mistakes:

• Confusing with finding max or min subset sums
• Thinking about number of subsets instead of sums
• Assuming sum of all elements is the answer

2. Which of the following JavaScript function signatures is correct to start solving the Partition Equal Subset Sum problem?

easy

A. function partition(nums, sum) {}

B. function partitionEqualSubsetSum() {}

C. function canPartition(nums) {}

D. function canPartition(nums, target) {}

Solution

1. Step 1: Identify typical function signature

   The problem usually takes one parameter: an array of numbers to check partitioning.

2. Step 2: Match options with typical usage

   function canPartition(nums) {} uses a clear, common name and one parameter for the array. Others add extra parameters or use less common names.

3. Final Answer:

   function canPartition(nums) {} -> Option C

4. Quick Check:

   Function with one array parameter = function canPartition(nums) {} [OK]

Hint: Use one array parameter named nums for input [OK]

Common Mistakes:

• Adding unnecessary parameters like target or sum
• Using unclear or inconsistent function names
• Missing the array parameter

3. What will be the output of the following code snippet?

function canPartition(nums) {
  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];
}

console.log(canPartition([1, 5, 11, 5]));

medium

A. false

B. true

C. undefined

D. TypeError

Solution

1. Step 1: Calculate total and check parity

   Sum is 1+5+11+5 = 22, which is even, so continue.

2. Step 2: Use dynamic programming to check subset sum

   Target is 11. The dp array tracks sums possible. The subset [11] or [5,5,1] sums to 11, so dp[11] becomes true.

3. Final Answer:

   true -> Option B

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 total sum is even
• Iterating dp array forward instead of backward
• Returning wrong dp index

4. Identify the bug in this code snippet for Partition Equal Subset Sum:

function canPartition(nums) {
  const total = nums.reduce((a, b) => a + b);
  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 = num; j <= target; j++) {
      dp[j] = dp[j] || dp[j - num];
    }
  }
  return dp[target];
}

medium

A. Missing initial value in reduce causes error

B. dp array size is incorrect

C. dp[0] should be false initially

D. Inner loop should run backward from target to num

Solution

1. Step 1: Check reduce usage

   Reduce without initial value works if array not empty, so no error here.

2. Step 2: Analyze inner loop direction

   Loop runs forward (j = num to target), which causes dp to use updated values in same iteration, leading to incorrect results. It should run backward to avoid reuse.

3. Final Answer:

   Inner loop should run backward from target to num -> Option D

4. Quick Check:

   Loop backward to avoid dp overwrite [OK]

Hint: Loop backward in dp to prevent using updated states [OK]

Common Mistakes:

• Running dp loop forward causing wrong results
• Assuming reduce needs initial value always
• Incorrect dp array initialization

5. Given the array [2, 2, 3, 5], which of the following modifications to the Partition Equal Subset Sum algorithm will correctly determine if the array can be partitioned into two equal sum subsets, considering the edge case where the total sum is odd?

hard

A. Add a check to return false immediately if the total sum is odd before running dp

B. Change dp array to track counts of subsets instead of booleans

C. Use recursion without memoization to explore all subsets

D. Ignore the total sum parity and run dp directly

Solution

1. Step 1: Calculate total sum and check parity

   Sum is 2+2+3+5 = 12, which is even, so partitioning is possible in theory.

2. Step 2: Importance of parity check before dp

   If sum is odd, no equal partition exists. Checking this early saves time and avoids unnecessary dp computation.

3. Step 3: Evaluate options for correctness

   Add a check to return false immediately if the total sum is odd before running dp correctly adds this check. Change dp array to track counts of subsets instead of booleans changes dp meaning incorrectly. Use recursion without memoization to explore all subsets is inefficient. Ignore the total sum parity and run dp directly ignores parity, causing wrong results.

4. Final Answer:

   Add a check to return false immediately if the total sum is odd before running dp -> Option A

5. Quick Check:

   Check sum parity before dp = Add a check to return false immediately if the total sum is odd before running dp [OK]

Hint: Always check if total sum is even before dp [OK]

Common Mistakes:

• Skipping sum parity check causing wrong answers
• Changing dp logic unnecessarily
• Using slow recursion without memoization