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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Partition Equal Subset Sum Check

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

DSA Typescript

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];
}

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

A true

B false

C TypeError

D SyntaxError

💡 Hint

Think about whether the total sum is even and if a subset sums to half the total.

The total sum is 22, which is even. The subset [11, 5] sums to 16, but the correct subset is [1, 5, 5, 11] partitioned as [1, 5, 5] and [11]. The function returns true because such a partition exists.

❓ Predict Output

intermediate

Result of Partition Check on Odd Sum Array

What will be the output of this code snippet checking partition possibility for an array with an odd total sum?

DSA Typescript

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];
}

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

A true

B ReferenceError

C RangeError

D false

💡 Hint

Check if the total sum is even or odd.

The total sum is 11, which is odd. Since the sum is odd, it's impossible to split into two equal subsets, so the function returns false.

🧠 Conceptual

advanced

Understanding the DP Array in Partition Equal Subset Sum

In the Partition Equal Subset Sum problem, what does the boolean array 'dp' represent during the dynamic programming process?

A 'dp[j]' counts the number of subsets that sum to 'j'.

B 'dp[j]' is true if a subset of the input array sums exactly to 'j', false otherwise.

C 'dp[j]' stores the minimum number of elements needed to sum to 'j'.

D 'dp[j]' is true if all subsets sum to 'j', false otherwise.

💡 Hint

Think about what the boolean values track in the subset sum problem.

The dp array tracks whether it is possible to form a subset with sum 'j'. If dp[j] is true, it means some subset sums exactly to 'j'.

🔧 Debug

advanced

Identify the Bug in Partition Equal Subset Sum Implementation

What error will this code produce when run, and why?

DSA Typescript

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).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, 2, 3, 4]));

A ReferenceError: dp is not defined

B RangeError: Invalid array length

C TypeError: Cannot set property '0' of undefined

D undefined (returns false)

💡 Hint

Check how the dp array is initialized and accessed.

The dp array is created with length 'target' but accessed at index 'target', which is out of bounds. Setting dp[0] works, but dp[target] causes an error because dp[target] is undefined.

🚀 Application

expert

Maximum Subset Sum Less Than or Equal to Target

Given the Partition Equal Subset Sum problem, how would you modify the algorithm to find the maximum subset sum less than or equal to half the total sum if equal partition is not possible? Which option correctly describes the approach?

A Use the dp array to track all achievable sums and return the largest index 'j' where dp[j] is true and j <= target.

B Sort the array and pick elements greedily until sum exceeds half the total sum.

C Use recursion without memoization to try all subsets and pick the maximum sum less than or equal to target.

D Return the sum of all elements divided by two without checking subsets.

💡 Hint

Think about how the dp array can be used to find achievable sums.

The dp array tracks which sums are possible. By scanning dp from target down to 0, the largest achievable sum less than or equal to target can be found efficiently.