# multiset variant of subset sum problem known algorithms

I have been working in the time analysis for an exact solver I designed for the subset sum problem accepting multisets as input instances, and determined its time complexity to be dependent on the multiplicity ($$m$$) of the elements in the input.

For input instances containing elements having $$m \leq 2$$, the time complexity is $$O(2^{n/2} \cdot 0.75^{\frac{d/2}{n}})$$ where $$d=$$ # of elements with $$m=2$$.

For example, when $$d=n/2$$, then:

• $$O(2^{n/2} \cdot 0.75^{\frac{d/2}{n}}) \approx O((1.4142 \cdot 0.93)^n) \approx O(1.316^n)$$

For input instances containing elements having $$m = 1$$ and $$m=4$$, the time complexity is $$O(2^{n/2} \cdot 0.312^{\frac{d/2}{n}})$$ where $$d=$$ # of elements with $$m=4$$.

For example, when $$d=n/4$$, then:

• $$O(2^{n/2} \cdot 0.312^{\frac{d/2}{n}}) \approx O((1.4142 \cdot 0.86)^n) \approx O(1.223^n)$$

And following the above configuration, for $$m=8$$ and $$d=n/8$$ is

• $$O(2^{n/2} \cdot 0.035^{\frac{d/2}{n}}) \approx O((1.4142 \cdot 0.81)^n) \approx O(1.147^n)$$

I have yet to complete the time analysis for mixed cases (different multiplicities in the input instance) but my educated guess is it will be a composite of the above TCs.

Besides to ask for comments, I am looking as well for other known algorithms with a similar behavior to compare approaches (looked for them but found nothing so far...)