Partition Equal Subset Sum in DSA Typescript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to check if the total sum is even.

DSA Typescript

const totalSum = nums.reduce((acc, num) => acc + num, 0);
if (totalSum [1] 2 !== 0) {
  return false;
}

Drag options to blanks, or click blank then click option'

A/

B*

C%

D+

Attempts:

3 left

💡 Hint

Common Mistakes

Using division (/) instead of modulus (%) to check evenness.

Using multiplication (*) or addition (+) which do not check divisibility.

We use the modulus operator % to check if the total sum is divisible by 2 (even).

2fill in blank

medium

Complete the code to initialize the target sum for subset search.

DSA Typescript

const target = totalSum [1] 2;

Drag options to blanks, or click blank then click option'

A/

B-

C+

D*

Attempts:

3 left

💡 Hint

Common Mistakes

Multiplying instead of dividing.

Adding or subtracting which changes the target incorrectly.

We divide totalSum by 2 to find the target sum for one subset.

3fill in blank

hard

Fix the error in the loop that updates the dp array for subset sums.

DSA Typescript

for (let num of nums) {
  for (let j = target; j >= [1]; j--) {
    dp[j] = dp[j] || dp[j - num];
  }
}

Drag options to blanks, or click blank then click option'

Atarget

Bnum

C1

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Starting inner loop from 0 which causes incorrect dp updates.

Starting from target or 1 which does not prevent overwriting.

We start from target down to num to avoid using updated dp values in the same iteration.

4fill in blank

hard

Fill both blanks to create a dp array and initialize the base case.

DSA Typescript

const dp: boolean[] = new Array([1] + 1).fill(false);
dp[[2]] = true;

Drag options to blanks, or click blank then click option'

Atarget

B0

C1

Dnums.length

Attempts:

3 left

💡 Hint

Common Mistakes

Initializing dp size with nums.length instead of target.

Setting dp[1] = true instead of dp[0].

We create dp array of size target+1 and set dp[0] = true as base case (sum 0 is always possible).

5fill in blank

hard

Fill all three blanks to complete the function that returns if partition is possible.

DSA Typescript

function canPartition(nums: number[]): boolean {
  const totalSum = nums.reduce((acc, num) => acc + num, 0);
  if (totalSum [1] 2 !== 0) return false;
  const target = totalSum [2] 2;
  const dp: boolean[] = 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[[3]];
}

Drag options to blanks, or click blank then click option'

A%

B/

Ctarget

D0

Attempts:

3 left

💡 Hint

Common Mistakes

Using wrong operators for checking evenness or division.

Returning dp[0] or dp[num] instead of dp[target].

We check if totalSum % 2 !== 0, divide totalSum by 2 for target, and return dp[target].

Practice

1. What does the Partition Equal Subset Sum problem ask you to find?

easy

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

B. If the array contains any duplicate elements

C. If the array is sorted in ascending order

D. If the array has an even number of elements

Solution

1. Step 1: Understand the problem goal

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

2. Step 2: Clarify what is being checked

   It is not about duplicates, sorting, or count of elements, but about equal sum partitioning.

3. Final Answer:

   If 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: Focus on equal sum subsets, not element order or duplicates [OK]

Common Mistakes:

• Thinking it checks for duplicates
• Confusing with sorting problems
• Assuming it checks array length parity

2. Which of the following TypeScript function signatures correctly represents a function to solve Partition Equal Subset Sum?

easy

A. function canPartition(nums: boolean[]): boolean

B. function canPartition(nums: string): number

C. function canPartition(nums: number): string

D. function canPartition(nums: number[]): boolean

Solution

1. Step 1: Identify correct parameter type

   The input is an array of numbers, so nums: number[] is correct.

2. Step 2: Identify correct return type

   The function returns true or false, so return type is boolean.

3. Final Answer:

   function canPartition(nums: number[]): boolean -> Option D

4. Quick Check:

   Input array of numbers, output boolean [OK]

Hint: Input is number array, output is boolean for yes/no [OK]

Common Mistakes:

• Using wrong input type like string or boolean array
• Returning number instead of boolean
• Incorrect function signature syntax

3. What is the output of the following TypeScript code?

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

medium

A. Runtime error

B. true

C. undefined

D. false

Solution

1. Step 1: Calculate total sum and check parity

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

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

   The code checks if a subset sums to 11 (half of 22). 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 exists = true [OK]

Hint: Check if half sum subset exists using dp array [OK]

Common Mistakes:

• Not checking if total sum is even
• Confusing dp array update direction
• Assuming false because of large numbers

4. Find the bug in this TypeScript code for Partition Equal Subset Sum:

function canPartition(nums: number[]): boolean {
  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 on empty array

B. dp array size is incorrect

C. Loop direction in inner for loop should be reversed

D. No bug, code is correct

Solution

1. Step 1: Check reduce usage

   Reduce lacks initial value, but if array is non-empty, it works. Not the main bug.

2. Step 2: Check inner loop direction

   The inner loop runs from num to target increasing, but it should run backward from target down to num to avoid using updated dp values in the same iteration.

3. Final Answer:

   Loop direction in inner for loop should be reversed -> Option C

4. Quick Check:

   Inner loop must go backward to avoid dp overwrite [OK]

Hint: Inner loop for dp must run backward to prevent reuse [OK]

Common Mistakes:

• Not reversing inner loop causes wrong dp updates
• Assuming reduce always needs initial value
• Ignoring dp array size correctness

5. Given the array [2, 2, 3, 7], which of the following subsets can be one half of the partition if the array can be split into two equal sum subsets?

hard

A. [2, 2, 3]

B. [2, 3]

C. [5]

D. [3, 5]

Solution

1. Step 1: Calculate total sum

   Sum = 2 + 2 + 3 + 7 = 14. Half sum = 7.

2. Step 2: Find subset summing to 7

   Check each option:
   A: [2,3] = 5 ≠ 7
   B: [2,2,3] = 7 == 7
   C: [5] = 5 ≠ 7 (5 not in array)
   D: [3,5] = 8 ≠ 7 (5 not in array)
   B works, with remaining [7] also 7.

3. Final Answer:

   [2, 2, 3] -> Option A

4. Quick Check:

   Sum half is 7, B sums to 7 [OK]

Hint: Sum array, find subset with half sum [OK]

Common Mistakes:

• Not calculating half sum correctly
• Choosing subsets that don't sum to half
• Ignoring that partition may not exist