I have an array list of distinct positive integers representing a set L, and an integer S. What's the fastest way to count all subsets of L which have the sum of their elements equal to S, instead of iterating over all subsets and just checking if each subset's sum equal is equal to S?
This can be solved in O(NS) using a simple dynamic programming approach, similar to knapsack problem. Let's for each Q and for each i solve the following problem: how many subsets of first i elements of L exist so that their sum is equal to Q. Let us denote the number of such subsets C[i,Q].
Obviously, C[0,0]=1 and C[0,Q]=0 for Q!=0. (Note that i=0 denotes first 0 elements, that is no elements.)
For a bigger i we have two possibilities: either the last available element (L[i-1]) is taken to our set, then we have C[i-1, Q-L[i-1]] such sets. Either it is not taken, then we have C[i-1, Q] such sets. Therefore, C[i,Q]=C[i-1, Q-L[i-1]]+C[i-1, Q]. Iterating over i and Q, we calculate all Cs.
Note that if all elements in L are non-negative, then you can solve the problem only for non-negative Qs, and the first term disappears if Q<L[i-1]. If negative elements are allowed, then you need to consider negative Qs too.