Subset-sum problem is in NP

Statement

Lemma

Subset-sum problem is in NP.

Proof

It is of the format to be a search problem as it either returns a result or it says no such result exists.

Suppose we are given an instance for and . To verify a solution make the check

this takes time. Therefore this takes polynomial time.