  The subset sum problem is known to be an NP-hard problem in the field of
computer science with the fastest known approach having a run-time complexity
of $O(2^{0.3113n})$. A modified version of this problem is known as the perfect
sum problem and extends the subset sum idea further. This extension results in
additional complexity, making it difficult to compute for a large input. In
this paper, I propose a probabilistic approach which approximates the solution
to the perfect sum problem by approximating the distribution of potential sums.
Since this problem is an extension of the subset sum, our approximation also
grants some probabilistic insight into the solution for the subset sum problem.
We harness distributional approximations to model the number of subsets which
sum to a certain size. These distributional approximations are formulated in
two ways: using bounds to justify normal approximation, and approximating the
empirical distribution via density estimation. These approximations can be
computed in $O(n)$ complexity, and can increase in accuracy with the size of
the input data making it useful for large-scale combinatorial problems. Code is
available at https://github.com/KristofPusztai/PerfectSum.
