Partition Equal Subset Sum in DSA Typescript - Build from Scratch

Partition Equal Subset Sum

📖 Scenario: You have a collection of items, each with a weight. You want to see if you can split these items into two groups so that both groups weigh the same. This is like trying to pack two bags with the same total weight.

🎯 Goal: Build a program that checks if the given list of numbers can be divided into two parts with equal sums.

📋 What You'll Learn

Create an array called nums with the exact values: [1, 5, 11, 5]

Create a variable called target that holds half of the total sum of nums

Write a function called canPartition that takes nums and target and returns true if a subset sums to target, otherwise false

Print the result of calling canPartition(nums, target)

💡 Why This Matters

🌍 Real World

This problem is like packing two bags with equal weight, useful in logistics and resource allocation.

💼 Career

Understanding subset sum problems helps in algorithm design, coding interviews, and solving optimization problems.

1

Create the number array

Create an array called nums with these exact numbers: 1, 5, 11, and 5.

DSA Typescript

# Your code here

Hint

Use square brackets [] to create an array and separate numbers with commas.

2

Calculate the target sum

Create a variable called target that holds half of the total sum of the numbers in nums. Use nums.reduce((a, b) => a + b, 0) to get the total sum.

DSA Typescript

const nums = [1, 5, 11, 5];
// Your code here

Hint

Use reduce to sum all numbers, then divide by 2.

3

Write the partition check function

Write a function called canPartition that takes nums and target as parameters. Use a boolean array dp of size target + 1 to track reachable sums. Initialize dp[0] to true. For each number in nums, update dp from target down to the number, setting dp[j] to dp[j] || dp[j - num]. Return dp[target] at the end.

DSA Typescript

const nums = [1, 5, 11, 5];
const target = nums.reduce((a, b) => a + b, 0) / 2;
// Your code here

Hint

Use a dynamic programming array to track sums you can make. Start with dp[0] = true because sum zero is always possible.

4

Print the partition result

Print the result of calling canPartition(nums, target) using console.log.

DSA Typescript

const nums = [1, 5, 11, 5];
const target = nums.reduce((a, b) => a + b, 0) / 2;

function canPartition(nums: number[], target: number): boolean {
    if (!Number.isInteger(target)) return false;
    const dp: boolean[] = 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];
}
// Your code here

Hint

Use console.log(canPartition(nums, target)) to show the result.