Dynamic Programming

Subset Sum

This is an important problem. We all know how to solve two-sum, or even three-sum, where you just use a hash-map, but what about a sum to an arbitrary number ?

  • Don’t you just continuously apply the target values in the hash map

Good set of notes to talk about this problem: https://cs.uwaterloo.ca/~lapchi/cs341/notes/L11.pdf

But that would be way too slow.

The insight is that we don’t need to keep track of which subset we have chosen so far, as long as they have the same sum.

  • I mean that is obvious