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.

Sort the array.

Edit. Oops I guess I should not give too much details for hints. You can check full solution on edit history.

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'$$$?