Mathematica Stack Exchange is a question and answer site for users of Mathematica. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Suppose I have a list of positive integers:

data={1, 1, 2, 3, 3, 3, 5, 5, 5, 7, 7, 8, 8, 9, 10, 10, 12, 16, 23}

I want to count the number of subsets up to length t (including an empty set) whose total doesn't exceed the value t.

The naive approach would be:

sumZaehl[t_, data_] :=
  Length@Select[Total /@ Subsets[data, t], # <= t &]

But this would not work for larger list, because of the rapidly increasing number of subsets. I have an iterative method which works for larger list too:

sumZaehlIter[t_, data_] :=
Module[{n = Length[data], v, d, i, j},
  For[i = 0, i <= t, i++, v[i] = 1];
  For[i = 1, i <= n, i++,
    d = data[[i]];
    For[j = t, j >= d, j--, 
       v[j] = v[j] + v[j - d]; 

Is there a functional way to realize this?

share|improve this question
I figure that the sublists with a total not greater than 3 are following six: {{},{1},{2},{3},{1,1},{1,2}}. Yet both your sumZaehlIter[3,data] and Leonid's v[3,data] return 10. What are the other four sublists with a total not greater than 3? – DavidC Mar 6 '12 at 3:29
@David, I think (with multiplicities of some elements), there are two additional occurences of {3} and one additional occurence for each of {1} and {2,1}. – kglr Mar 6 '12 at 7:57
@kguler Interesting. So it has nothing to do with the order of the elements within a sublist? – DavidC Mar 6 '12 at 10:14
@David, yes; so the complete collection is {{},{1},{1},{2},{3},{3},{3},{1,1},{1,2},{1,2}}. – kglr Mar 6 '12 at 10:44
up vote 8 down vote accepted

This is not really the same algorithm, but

v[t_, data_] :=
     v[_?Negative, _] := 0;
     v[_, 0] := 1;
     v[tl_, n_] := v[tl, n] =
        v[tl - data[[n]], n - 1] + v[tl, n - 1];
     v[t, Length[data]]

You may need to increase the $RecursionLimit for larger lists.

share|improve this answer
the iterative Module works quite well but I'm interested in functional. With the "naive" way I get errors "Subset::toomany and "must be a machine integer". Why "a machine integer" – Peter Breitfeld Mar 5 '12 at 20:38
@Peter Your iterative algorithm uses a lot of mutable state. While you probably can achieve the same with the functional constructs, I suspect that the direct translation of it into functional would be either inefficient or resulting in a thin functional facade over the essentially procedural core. The algorithm I posted above has the same underlying idea as yours, but IMO is a functional version of it (although not a direct translation), using recursion and memoization. A similar situation happens e.g. with the longest common sequence algorithm. – Leonid Shifrin Mar 5 '12 at 21:03
That's beautiful. +1 – Mr.Wizard Mar 6 '12 at 8:10
Nice solution! +1 – Pillsy Mar 6 '12 at 16:08
@Pillsy, Mr.Wizard Thanks! – Leonid Shifrin Mar 6 '12 at 17:11

Ah, came across this from the "related" bar, time for a necro :-}

Here's a direct and fast one-liner:

numSST[t_, s_] := Block[{p = Normal[Times @@ (1 + x^s) + O[x]^(t + 1)], x = 1}, p];
share|improve this answer
@ciao...I really enjoyed this one-liner... – ubpdqn Aug 23 '15 at 11:25
Nice use of O[]. ;) – J. M. Aug 23 '15 at 11:33

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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