I am trying to reduce Exact Cover to Fixed Exact Cover to show that Fixed Exact Cover is NP-Hard.

**Exact Cover**

**Input**

S = {x_{1}, x_{2}, …, x_{n}} (set)

P = {P_{1}, P_{2}, …, P_{m}} (subsets of S)

**Decision problem**: Is there a subset {P_{i1},P_{i2},…,P_{iq}} of P such that every element of S belongs to exactly one of the P_{ij}:s?

**Fixed Exact Cover**

**Input** S, P from Exact Cover, and an integer **K**

**Decision problem**: Is there a subset {P_{i1},P_{i2},…,P_{ik}} of P of size K such that every element of S belongs to exactly one of the P_{ij}:s?

Given hint: **K = n + 1**

My initial reaction is to iterate through each element in S, and for each element create a subset for P. However, that will result result in K being one too small. I have tried many things, but I just can’t seem to figure it out.