Show that the subset sum problem (Given a sequence of integers $S=i_1, i_2, \dots , i_n$ and an integer $k$, is there a subsequence of $S$ that sums to exactly $k$?) is NP-complete.
Hint: Use the exact cover problem.
The exact cover problem is the following: Given a family of sets $S_1, S_2, \dots , S_n$ does there exist a set cover consisting of a subfamily of pairwise disjoint sets?
First of all, to show that this problem is in $\mathcal{NP}$ do we have to do the following?
A nondeterministic Turing machine can first guess which the subsequence of that we are looking for is and then verify that it sums to exactly k in linear time. Is this correct?
To show that it is NP-complete how could we reduce the exact cover problem to subset sum? Is it as follows?
The exact cover problem has a solution iff every element is in exactly one set.
We consider the set $S$ and the number $k$ such that each number corresponds to a set of elements and $k$ corresponds to the whole set. Suppose there are $n$ elements and $k$ different sets.
We replace each set S with a number that is $1$ in its ith position if i is in S and has a $0$ in its ith position otherwise.
We set k to a number that is $n$ copies of the number $1$.