You don't need a reduction; the problem you describe is known as EXACT COVER and it is one of the 21 decision problems Richard Karp proved $NP$-complete in 1972.
From Wikipedia:
Given a collection $S$ of subsets of a set $X$, an exact cover of $X$ is a subcollection $S^*$ of $S$ that satisfies two conditions:
- The intersection of any two distinct subsets in $S^*$ is empty, i.e., the subsets in $S^*$ are pairwise disjoint. In other words, each element in $X$ is contained in at most one subset in $S^*$.
- The union of the subsets in $S^*$ is $X$, i.e., the subsets in $S^*$ cover $X$. In other words, each element in $X$ is contained in at least one subset in $S^*$.
$X$ is the collection of letters on the refrigerator.
$S$ is the collection of words that your daughter knows that are made up of letters in $X$.
$S^*$ is a subcollection of words from $S$ that exactly cover $X$.
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
Best Answer
In 3D-Matching, we are given $X, Y, Z, T$ where:
1) $X, Y$ and $Z$ are 3 disjoint sets, each of size n.
2) $T = \{(x, y, z)\;:\; x \in X, y \in Y, z \in Z \} \subseteq X \times Y \times Z$
and we have to find M such that:
1) $M \subseteq T$
2) $|M| = n$
3) For any 2 distinct elements of M, $(x,y,z)$ and $(x', y', z')$, $x \neq x', y \neq y' $ and $z \neq z' $
In Exact-Cover, we are given a collection S, k where:
1) S is a collection of subsets of some Universe U with $\cup S=$U
and we have to find $S' = \{S_1, S_2, ..., S_k\} \subseteq S$ such that:
1) The elements in $S'$ are pairwise disjoint
2) $\cup S_i=\;$U
The reduction from 3D-Matching to Exact-Cover is:
Let $S = \{\;\{x, y, z\}\;:\;(x,y,z) \in T\}$
Let $k = |X| = |Y| = |Z| = n$
Now, we prove why the reduction works:
Suppose M is a solution to 3D-Matching.
Let $S' = \{ \{ x,y,z \}: (x,y,z) \in M \}$
Since, $|M|=n$, we have $|S'|=n=k$
We know that if $(x, y, z)$ and $(x', y', z')$ are 2 distinct elements in $M$
that $x \neq x', y \neq y'$ and $z \neq z'$ and since, $X, Y, Z$ are disjoint, this means $\{x,y,z \} \cap \{x', y', z' \} = \emptyset$.
That is, the elements in $S'$ are pairwise disjoint.
Also, $\cup S=$ U = $\cup S'$. Hence, $S'$ covers U.
Hence, $S'$ is a solution to Exact-Cover.
Now, suppose that $S' = \{S_1, S_2, ..., S_k \}$ is a solution to Exact-Cover.
Let $M = \{ (x, y, z): \{ x,y,z \} = S_i\;for\; i=1,2,..k\}$
Since, the $S_i$'s are pairwise disjoint, if (x, y, z) and (x', y', z') are 2 distinct elements of M, it follows that $x \neq x', y \neq y'$ and $z \neq z'$.
Hence, M is a solution to 3D-Matching.