I am looking for the number of possible outcomes given to a set of numbers X that sum to Y. This is the same issue as here. However, I would like to consider that (i) the numbers can't be repeated and (ii) the order doesn't matter. For example, the only possible outcome for:
- 4: [3,1] given the list [3,2,1]
- 5: [[4,1],[3,2]] given the list [4,3,2,1]
An implementation in Python with the possible answers is given here (Answer 2), If a list with ascending or descending order without repetitions is passed the problem is the same as the examples above. However, what I want is just the possible number of answers.
I'm afraid that cannot be computed easily. Even deciding if the number of solutions is greater than 0 is known as the subset sum problem which is NP-complete, so finding the exact number of solutions is at least as hard.
If the set is small, simply trying all subsets could be a solution, and for larger sets otherwise, there are other algorithms, eg. this.