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$
$\endgroup$
8
-
$\begingroup$ You can calculate this easily using dynamic programming. Try it out. $\endgroup$– Yuval FilmusDec 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$– TheNotMeDec 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$– Albert HendriksDec 19, 2017 at 21:25
-
$\begingroup$ @AlbertHendriks maybe I am missing your point but you can always take the singleton {k} $\endgroup$– TheNotMeDec 19, 2017 at 21:31
-
$\begingroup$ @AlbertHendriks You can easily prove this by induction. $\endgroup$– Yuval FilmusDec 19, 2017 at 21:32
|
Show 3 more comments
1 Answer
$\begingroup$
$\endgroup$
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.
answered Dec 19, 2017 at 21:38