Knapsack problem NP-complete Show that the knapsack 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 follwing:
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?
(Set cover: Given a family of sets $S_1, S_2, \dots , S_n$ does there exist a subfamily of $k$ sets $S_{i_1}, S_{i_2}, \dots , S_{i_k}$ such that $\cup_{j=1}^k S_{i_j}=\cup_{j=1}^n S_j$ ? )
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??
We know that the exact cover problem has solution iff each element of the set $X$ is in exactly one subset $S_i$, right? 
To reduce this problem to the Knapsack problem do we have to map the subsets $S_j$ to the integers $i_j$ ??
Or is there an other way to reduce the exact cover problem to the Knapsack problem?? 
EDIT: 
Can I formulate the reduction as followed?? 

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?
The Set cover is the following: 
  Given a family of sets $S_1, S_2, \dots , S_n$ does there exist a subfamily of $\lambda$ sets $S_{i_1}, S_{i_2}, \dots , S_{i_{\lambda}}$ such that $\cup_{j=1}^{\lambda} S_{i_j}=\cup_{j=1}^n S_j$ ? 

We will reduce the Exact Cover problem to the Knapsack problem.
Let $A=\{a_1, a_2, \dots , a_m\}$ and $A_1, A_2, \dots , A_{\lambda}$, be the set and the subsets of an instance of the Exact Cover problem.
We will construct an instance of the Knapsack problem in polynomial time.
That means that we will construct the integers $i_1, i_2 \dots , i_n$ and the integer $k$ such that there is a subset $P \subseteq \{1, \dots , n\}$ with $\sum_{j \in P} i_j=k$ iff there is a family of $\lambda$ pairwise disjoint sets that covers the whole $A$. 
Each of the $\lambda$ subsets $A_j$ corresponds to an integer with $\lambda$ digits, $e_{j1} \dots e_{j \lambda}$ in the base $\lambda+1$, where $e_{ji}=1$ if $a_i \in A_j$ and $e_{ji}=0$ otherwise. 
So, we have $\lambda$ integers $i_1, \dots , i_{\lambda}$ where $i_j=\sum_{r=1}^{\lambda}e_{jr}(\lambda+1)^{r-1}$.
We set $k=\sum_{r=0}^{\lambda-1}(\lambda+1)^r$.
So, the question is whether there is a subset the terms of which sum to exactly $k$, that means to $\underbrace{111 \dots 1}_{\lambda}$. 
Therefore, this instance of the Knapsack problem has a solution iff the initial instance of the Exact Cover problem has a solution. 
The reduction is polytime because p(n) steps are needed to "translate" any input of the Exact Cover problem into an input of the Knapsack problem, where p(n) is some polynomial
Is it correct?? 
Could I improve something?? 
Are the indices that I used correct?? 
 A: The Knapsack problem is NP, and any problem in NP can be reduced to an NP complete problem (Cook's Theorem). So to show that the knapsack problem is NP complete it is sufficient to show that an NP-complete problem is reducible to the Knapsack problem. We want to use the exact cover problem to show this. A lot of such reductions can be found in the paper of Karp[1], including the reduction that is described here. 
My notation conforms mostly to the notation in this paper.
Assume that $\{S_j,j=1,\ldots,p\}$ is a family of sets that covers the set 
$U=\{u_i,i=1,\ldots,t\}$, so 
$$\cup_{j=1}^{m} S_j=U$$ 
We want to check if there is a subfamily $\{S_{j_h},h=1,\ldots,q\}$ of $\{S_j,j=1,\ldots,p\}$ that covers $U$ and where the members of these family are pairwise disjoint.  Let $d$ be an arbitrary positive integer. We can assign the number
$$\; \epsilon_{i,j}= \begin{cases}
0,& u_i \not \in S_j \\
1, &  u_i \in S_j
\end{cases} \\
 a_j=\sum_{j=1}^m \epsilon_{i,j} d^{i-1} \tag{1}$$
to a subset $S_j$.
So $a_j$ is a number that can be written only with digits $0$ and $1$ in a number system with base $d$. It has the digit $1$ on position $i-1$ if and only if  $u_i \in S_j$. If $a_{j_1}$ and $a_{j_2}$ are to values assigned to two sets of an exact cover, then there is no position in the representation as an $d$ base number, where both numbers have the digit $1$. The sum $b$ of all the numbers assigned to an exact cover is 
$$b=\sum_{i=1}^{t}d^{i-1} \tag{2}$$
if $\{S_j,j=1,\ldots,p\}$ has an exact cover $\{S_{j_h},h=1,\ldots,q\}$ then $x=(x_1,\cdots,x_p)$ with 
$$ x_j=
\begin{cases}
1 & \text{if}\; j=j_h, \text{for an } h \in \{1,...,q\} \\
0 & \text{if}\; j\ne j_h, \text{for all } h \in \{1,...,q\} \\
\end{cases}$$
is one solution of the
of the 0-1-Knaspack problem
$$\sum_{i=1}^{p} a_i x_i=b$$
where $a_j$ and $b$ are defined in $(1)$ and $(2)$.
If we select the base $d=p+1$ (or larger) fo all the $2^p$ 0-1-sums no carry will occurr when adding them. So when ome of them sum up to be, there summands con't have 1s on the same place.
[1]  Richard M. Karp: Reducibility Among Combinatorial Problems
In: R. E. Miller and J. W. Thatcher (Hrsg.): Complexity of Computer Computations. 
Plenum Press, New York, 1972, 
p. 85–103
A: I'll show a possible mapping from exact cover to knapsack by example. Consider a particular exact cover problem consisting of $n=4$ elements $\langle x_0, x_1, x_2, x_3 \rangle$.
Now suppose we have a set $S_i = \{x_1, x_3\}$. We can alternatively represent $S_i$ with a $0/1$ list $L_i = \langle 0, 1, 0, 1 \rangle$ (the $j$-th element of $L_i$ is $1$ iff $x_j \in S_i$).
Now, construct a new list $T_i$ from $L_i$ by appending $n$ zeroes in front of every member. So, the list $L_i$ above would become $\langle 0, 0, 0, 0, *0*, 0, 0, 0, 0, *1*, 0, 0, 0, 0, *0*, 0, 0, 0, 0, *1* \rangle$ (I marked the "original" members by surrounding them with asterisks).
Now, consider the integer whose binary representation is $T_i$. We want to find a subset of these integers that sums exactly to $\langle 0, 0, 0, 0, *1*, 0, 0, 0, 0, *1*, 0, 0, 0, 0, *1*, 0, 0, 0, 0, *1* \rangle$. Clearly the "overflow" from sum carries cannot go beyond the $n$ zeroes.
Note: Actually appending $n$ zeroes is overkill. $\log n$ zeroes should be enough, but it doesn't matter.
