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