Postby **DavCrav** » Fri Jan 24, 2014 9:40 am UTC

In essence, you just want to know which subsets of X can add together to make a number n.

I don't know the most efficient algorithm to do this, but I needed this to solve a problem about possible decompositions of modules for algebraic groups, and thought up the following easy recursive algorithm.

function RestrictedDistinctPartitions(X,n)

1) Put X={x_1,\...,x_m} into ascending order, and write X'=X\{x_m}.

2) Call RestrictedDistinctPartitions(X',n) // this assumes x_m isn't in the set.

3) Call RestrictedDistinctPartitions(X',n-x_m ) // this assumes x_m is in the set.

4) Return the outputs of 2) and 3).

end function;

It should be faster than your method, I believe, but is still pretty slow.