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