Although finding the specific partitions might be tricker, existence is easy, this is the classic change making problem. Expand prod_i 1/(1-x^p_i) and check if

Although finding the specific partitions might be tricker, existence is easy, this is the classic change making problem. Expand prod_i 1/(1-x^p_i) and check if you have terms = total value. Should tell you the number of possible partitions right away.