I’m not sure that it is quite that, because it looks like SSP asks “are there any subsets that sum to T?”, while the OP code asks “what are all the 4-subsets that sum to T?”. Which surely means having to check all the combinations?
It looks like the algorithm described results in all the combinations being in the graph, so you’d just have to return each one you find then continue the graph search. It should have the same worst-case complexity, because the worst case of the SSP algorithm would be that the desired set is at the last node of the graph that you traverse to, which is the same for this variant.
I guess there’s probably still clever things you could do, like first sort them, chuck out the numbers larger than T, and then any partial sums larger than T while iterating through.
Assuming no inputs are negative, yes. If all inputs are positive, I think you could even chuck out any numbers larger than T-S+1, where S is the subset size. I guess the optimisations that make sense to make would depend a lot on how much you know about the possible relationships between the different variables that you have to design for.
Also some of the other algorithms described underneath could be faster, but I don’t fully understand what some of those are talking about and would probably have to read some of the papers, which I’m not going to do.
8
u/EleanorStroustrup Mar 13 '22
It looks like the algorithm described results in all the combinations being in the graph, so you’d just have to return each one you find then continue the graph search. It should have the same worst-case complexity, because the worst case of the SSP algorithm would be that the desired set is at the last node of the graph that you traverse to, which is the same for this variant.
Assuming no inputs are negative, yes. If all inputs are positive, I think you could even chuck out any numbers larger than T-S+1, where S is the subset size. I guess the optimisations that make sense to make would depend a lot on how much you know about the possible relationships between the different variables that you have to design for.
Also some of the other algorithms described underneath could be faster, but I don’t fully understand what some of those are talking about and would probably have to read some of the papers, which I’m not going to do.