4
$\begingroup$

I have a problem statement that seems to be a reduced version of the knapsack problem, but I don't know how do it in Mathematica.

The problem is as follows: Given a set, S, of integers (e.g {a,b,c,...}) and a specific integer T, find all the possible combinations of the elements of S that sum exactly to T. (e.g returns {a,d,e} and {e,f} because a+d+e=T and e+f=T).

$\endgroup$
2
  • $\begingroup$ Please add a specific example. Also, is KnapsackSolve not handling this? $\endgroup$ Commented Oct 25, 2020 at 21:29
  • $\begingroup$ An example such as s={1,2,4,5}; t=6; (*output: {{1,5},{2,4}} *) $\endgroup$ Commented Oct 27, 2020 at 15:00

1 Answer 1

11
$\begingroup$
Select[Subsets[s], Tr@# == t&]

Should accomplish what you're after.

If you'd like to allow multiset results,

IntegerPartitions[t, All, s]
$\endgroup$
2
  • 2
    $\begingroup$ You could also use ResourceFunction["SelectSubsets"] if memory usage becomes an issue (see Properties & Relations section). $\endgroup$
    – flinty
    Commented Oct 25, 2020 at 16:37
  • $\begingroup$ Wow. That's amazing. A one-liner for a combinatorics problem. Thank you. I made a slight change to fit better with my understanding, Select[Subsets[s], Total@# == t &] $\endgroup$ Commented Oct 27, 2020 at 14:58

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.