### EugeneJudo's blog

By EugeneJudo, history, 2 months ago,

I'm trying to solve https://cses.fi/problemset/task/2183, and I'm completely baffled since every approach I come up with looks to violate the subset sum problem being NP complete for finding a specific subset that sums to N. I'd appreciate a nudge in the right direction.

My observations so far:

• If $1,2,4,...,2^i$ are in $X$, then $MEX >= 2^{i+1}$

• $MEX <= 1 + (x_1 + \ldots + x_n)$

• $MEX = 1$ if $\min(X) > 1$

None of these observations seem sufficient in general.

• +8

 » 2 months ago, # | ← Rev. 2 →   +35 Sort the array.Edit. Oops I guess I should not give too much details for hints. You can check full solution on edit history.
•  » » 2 months ago, # ^ |   0 Thank you. For anyone who wants a bigger hint without the full solution, consider how if we know $X'$ has every subset sum up to $k$ but not $k+1$, then what do we know when we add a new element to $X'$?