Challenge - 5 Problems
Partition Equal Subset Sum Master
Get all challenges correct to earn this badge!
Test your skills under time pressure!
❓ Predict Output
intermediate2:00remaining
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]));Attempts:
2 left
💡 Hint
Think about whether the total sum is even and if a subset sums to half the total.
✗ Incorrect
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
intermediate2:00remaining
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]));Attempts:
2 left
💡 Hint
Check if the total sum is even or odd.
✗ Incorrect
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
advanced2:00remaining
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?
Attempts:
2 left
💡 Hint
Think about what the boolean values track in the subset sum problem.
✗ Incorrect
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
advanced2:00remaining
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]));Attempts:
2 left
💡 Hint
Check how the dp array is initialized and accessed.
✗ Incorrect
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
expert3:00remaining
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?
Attempts:
2 left
💡 Hint
Think about how the dp array can be used to find achievable sums.
✗ Incorrect
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.