CODEWITHSUNDEEP
calgorithm
Torsten Hĕrculĕ Cärlemän
Torsten Hĕrculĕ Cärlemän

Reputation: 239

Number of distinct sums of subsets

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.

Upvotes: 11

Views: 3401

Answers (2)

user2566092
user2566092

Reputation: 4661

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.

Upvotes: 2

amit
amit

Reputation: 178441

Using dynamic programming, you can find the number of distinct sums in O(n*MAX), where MAX is the maximal value in the array.

Let's look at the recursive function:

f(W,n,i) = f(W,n-1,i) OR (i != 0 ? f(W-item(n),n-1,i-1) : false)
f(0,0,0) = true
f(W,n,0) = false (W != 0)
f(W,0,i) = false (W != 0)
f(W,n,i) = false (W < 0)
(I have a feeling I forgot another failing base clause, so make sure if I didn't)

Now, if you build this bottom-up using Dynamic Programming, up to W=3*MAX, your answer is basically the number of different Ws that for them f(W,n,3) == true.

Building the table will be O(MAX*3 * n * 3) = O(MAX*n), the post-processing stage of counting the number of distinct Ws giving the desired sum is O(MAX), thus the solution remains O(MAX * n)

Upvotes: 1

Related Questions