Number of distinct sums of subsets

Question

I have a set of N, for N>3, distinct integers and the problem is to find all distinct sums of 3-subsets of the given set. A 3-subset is a subset whose cardinality is 3.

I know that the dumb way would be to do a cubic search on all possible sums and then sort out all duplicates. Is there a more efficient way to do this? I am programming in C.

EDIT: I wanted to know a general faster algorithm if say the number of elements were increased.

Answer 1

If you suspect that you may have lots of duplicate sums, then you can compute all distinct 2-subset sums first, and for each distinct 2-subset sum you find, keep track of which pair you have found that gave you the sum. If all your numbers are distinct, then if you ever find another pair that gives you the same sum, you should mark the sum as "multiple" and you can delete the pair you were storing for it if you like. Now you have a set of 2-subset sums, and each sum either has a single pair stored with it, or it is marked "multiple". For each 2-subset sum, if it's marked "multiple" then you iterate through all numbers in your original set and record all the 3-subset sums you can form by adding each number to your 2-subset sum. Otherwise, if the 2-subset sum is not marked "multiple" and you have a pair (a,b) associated with it, then you do the same thing except you skip a and b when you are iterating through your original set of numbers. This is how you get all distinct 3-subset sums. If you have n numbers and they make N distinct 2-subset sums, then the complexity of this approach is O(nN) if you use hash tables to detect duplicates at the two stages of the algorithm, which may be much better than the brute force O(n^3 log n), especially if you have a fairly dense set of integers.