# Subset Sum for {1,…,n}

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

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

## 1 Answer

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.