4
$\begingroup$

In general, the subset sum problem is NP-Complete. However, what if we say that our set is $\{1,...,n\}$? Is there a formula/combinatorial calculation that says how many subsets of $\{1,...,n\}$ have their sum equal to $k$?

$\endgroup$
  • $\begingroup$ You can calculate this easily using dynamic programming. Try it out. $\endgroup$ – Yuval Filmus Dec 19 '17 at 19:44
  • $\begingroup$ Of course I can, there is a dynamic programming algorithm for Subset Sum. My question is whether there exists a formula or a combinatorial reasoning for this since this is a trivial and fixed set. $\endgroup$ – TheNotMe Dec 19 '17 at 20:29
  • 1
    $\begingroup$ additionally, how to prove that there is at least one solution for every k <= 0.5n(n+1) ? $\endgroup$ – Albert Hendriks Dec 19 '17 at 21:25
  • $\begingroup$ @AlbertHendriks maybe I am missing your point but you can always take the singleton {k} $\endgroup$ – TheNotMe Dec 19 '17 at 21:31
  • $\begingroup$ @AlbertHendriks You can easily prove this by induction. $\endgroup$ – Yuval Filmus Dec 19 '17 at 21:32
1
$\begingroup$

This is A053632. The prefixes of this sequence convergence to the more well-known A000009, the number of partitions into distinct (or odd) parts. You shouldn't expect a clean formula, though it's of course easy to calculate small terms using dynamic programming.

$\endgroup$

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.