0
$\begingroup$

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?

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

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$.

Proof: [You may want to try it by yourself]

$\endgroup$
1
  • $\begingroup$ Thanks so much! $\endgroup$
    – joelsh
    Sep 14 at 2:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.