# Using FFT as a black box to solve subset sum. How is this done? Given a set of numbers, S, and a target value T

Given a set of numbers, S {s1, s2, ... sn} and a value T, I am looking to determine if any three elements in the set add up to value T. It is valid to have repeats like 2+2+2 would be fine for achieving a goal value of T=6. This is ultimately a decision problem of whether such a trio of values exists within the set that add up (with allowing repeats) to the target value.

The goal is to use FFT as a blackbox for solving the problem. I am at a complete loss here. How can FFT be used as a black box to solve subset sum?

• Looks like a homework problem to me. Sep 14 at 1:14
• Hint: Think in terms of polynomial multiplication. Sep 14 at 1:15
• @InuyashaYagami I am understanding the FFT and polynomial multiplication but I don't understand how this maps to subset sum Sep 14 at 1:47

For a set $$S = \{s_1,\dotsc,s_n\}$$. Construct a polynomial $$P(x): x^{s_1} + x^{s_2} + \dotsc + x^{s_n}$$.
Multiply the polynomial by itself three times, i.e., $$P(x) \cdot P(x) \cdot P(x)$$. Let this polynomial be $$Q(x)$$
Claim: The coefficient of $$x^T$$ in $$Q(x)$$ is non-zero if and only if there exist three values in $$S$$ that sum to $$T$$.