🗓️ Day 24: DP on Subsequences

🧠 Concept Deep Dive

Dynamic Programming on subsequences involves solving problems by either including or excluding elements from a sequence. The goal is to break down a decision at each step into: Do I take it or leave it? This leads to optimal substructures and overlapping subproblems—perfect for DP.

Classic examples:

0/1 Knapsack
Subset Sum
Target Sum
Partition Equal Subset Sum

These problems are foundational for building intuition with top-down memoization and bottom-up tabulation.

🎯 Visual Intuition (ASCII Diagram)

nums = [1, 5, 11, 5]
              ↓ include or exclude each

           ┌─── Take ──┐
   11 ← [1, 5, 11, 5] ←─┘
           └─ Don't ─→ 11

Each element decision branches recursively.

🛠️ Key Patterns

🧩 Pattern 1: Partition Equal Subset Sum (0/1 Knapsack)

Can we partition the array into two subsets of equal sum?

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 n = nums.length;
  const dp = Array(n + 1).fill(null).map(() => Array(target + 1).fill(false));

  for (let i = 0; i <= n; i++) dp[i][0] = true;

  for (let i = 1; i <= n; i++) {
    for (let j = 1; j <= target; j++) {
      if (nums[i - 1] <= j) {
        dp[i][j] = dp[i - 1][j] || dp[i - 1][j - nums[i - 1]];
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }

  return dp[n][target];
}

🧩 Pattern 2: Count of Subsets with Target Sum

How many ways can we form a target sum using elements?

function countSubsets(nums: number[], target: number): number {
  const dp = Array(nums.length + 1).fill(0).map(() => Array(target + 1).fill(0));
  for (let i = 0; i <= nums.length; i++) dp[i][0] = 1;

  for (let i = 1; i <= nums.length; i++) {
    for (let j = 0; j <= target; j++) {
      if (nums[i - 1] <= j) {
        dp[i][j] = dp[i - 1][j] + dp[i - 1][j - nums[i - 1]];
      } else {
        dp[i][j] = dp[i - 1][j];
      }
    }
  }

  return dp[nums.length][target];
}

📘 Example

Input: nums = [1, 5, 11, 5]

Total sum = 22 → Target = 11
Try to find a subset that sums to 11
One subset: [1, 5, 5], another: [11]
✅ Equal partition possible → return true

🧪 Homework

Given an array, return true if it can be partitioned into two subsets with equal sum.

function canPartition(nums: number[]): boolean {
  // your code here
}

console.log(canPartition([1, 5, 11, 5])); // true
console.log(canPartition([1, 2, 3, 5]));  // false

🧠 Big-O Cheat Sheet

Time Complexity: O(n * sum)
Space Complexity: O(n * sum) → Optimizable to O(sum)

🔮 Up Next

▶️ Day 25: Permutations – DFS on All Orders