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

  • $\begingroup$ You can calculate this easily using dynamic programming. Try it out. $\endgroup$ Dec 19, 2017 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, 2017 at 20:29
  • 1
    $\begingroup$ additionally, how to prove that there is at least one solution for every k <= 0.5n(n+1) ? $\endgroup$ Dec 19, 2017 at 21:25
  • $\begingroup$ @AlbertHendriks maybe I am missing your point but you can always take the singleton {k} $\endgroup$
    – TheNotMe
    Dec 19, 2017 at 21:31
  • $\begingroup$ @AlbertHendriks You can easily prove this by induction. $\endgroup$ Dec 19, 2017 at 21:32

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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