Skip to main content

Pattern 11: Subset Sum & Partition

The Target Sum Pattern: Can we select elements to hit a target sum? Minimize difference between partitions? Classic knapsack variants.

The Core Pattern​

THE MENTAL MODEL

Imagine dividing items into groups to achieve a specific total:

  1. Given numbers, can we select a subset that sums to target?
  2. Similar to 0/1 knapsack but focused on sum targets
  3. State tracks reachable sums with elements considered
  4. Common variants: equal partition, minimize difference, target sum with +/-
  5. Boolean DP (reachable?) or counting DP (how many ways?)

This is Subset Sum.

Pattern Recognition​

WHEN YOU SEE THIS PATTERN

Keywords: "subset sum", "partition", "target sum", "equal halves", "difference"

Structure:

  • Array of numbers
  • Need to select subset meeting sum constraint
  • Binary decision per element

State:

  • dp[i][sum] = "can we achieve sum using first i elements?"
  • OR dp[sum] = "is this sum reachable?"

Transitions:

  • Don't take element: dp[i-1][sum]
  • Take element: dp[i-1][sum - nums[i]]

Common Problems​

  • Partition Equal Subset Sum
  • Target Sum
  • Last Stone Weight II
  • Partition to K Equal Sum Subsets
  • Minimize Subset Sum Difference

(Example problems will be added here)