↓Skip to main content

Knapsack-Dp

LeetCode 4081: Prime Subset Selection II
·4 mins
LeetCode Hard Knapsack-Dp Number-Theory
LeetCode 4081 note: sieve the primes, then 0/1 knapsack with dp[j] the fewest primes summing to j; adding primes from large to small, a tie gives a smaller first element, so updating on <= yields the lexicographically smallest