Will this reduction of Exact Cover into Subset-Sum fail due to a potential false positive?

Question

After removing multi-sets and sets that have elements that don't exist in $S$.

$S$ = $[9,6,7,4,5,1,8]$

$C$ =$[[9,6,7],[4,5],[1,8]]$

Transform the values in $C$ of the shared index values with $S$. (This must be done before touching $S$)

$C$ = $[[1,2,3],[4,5],[6,7]]$

And do the same for $S$

$S$ = $[1,2,3,4,5,6,7]$

Square each $x$ integer in both $S$ and $C$

$f(x)$ = $x^2$, $x ∈ S$ then $C$

$S$ = $[1, 4, 9, 16, 25, 36, 49]$

$C$ = $[[1,4,9],[16,25],[36,49]]$

Then remove all sets with repeating sums to prevent false positives. This means no $[1],[1]s...$ that could be used, to sum up to the total sum of $S$, This also means $[1,4,9]$ or $[4,9,1]$. (leave one though!)

1. After the transformation is complete use subset-sum solver and define total-sum as $140$ (total-sum of $s$)
2. Define list of integers as a summed up set of $C$ = $[[14],[41],[85]]$
3. Run Algorithm and get the solution

Question

Will this reduction of Exact Cover into Subset-Sum every yield a false positive?

Answer 1

If you're not really sure whether a reduction will work, it probably won't. Whenever you are making a reduction you should always have a plan of how to prove it correct.

In this case, we're looking to see whether $1^2+2^2+3^2+...+n^2$ can be written as a sum of squares in some other way (which would be a false positive).

We have that $4^2=2^2+2^2+2^2+2^2$. This is enough to construct a counterexample.

Let $S=\{1,2,3,4,5,6,7\}$ and $C=\{\{1,2\},\{2,3\},\{2,5\},\{2,6\}\,\{2,7\},\{1,3,4,5,6,7\}\}$.

There is no exact cover (the only way to get $4$ is to take $\{1,3,4,5,6,7\}$ but then we cannot take any other set since all of them overlap).

However, we have that:

$$1^2+2^2+3^2+4^2+5^2+6^2+7^2=(1^2+2^2)+(2^2+3^2)+(2^2+5^2)+(2^2+6^2)+(2^2+7^2)$$

Thus, we can conclude the reduction does not work.