+ 4

# Name for set of numbers where all sums are different

Can anyone tell me if a set of N numbers where all possible sums are unique has a name? (e.g. {1,2,4} sums are 1, 2, 4, 3, 5, 6, 7 I would like to query if this has already been proposed as a challenge in sololearn

7 ответов

+ 7

bell
yes, while generating subsets along with sum there is good possibilty of duplicate sums, thatiswhy I wrote in my above comment to remove the duplicates.
You can store sum for each subset directly into a set to eliminate duplicate values
Here is link to lesson for it https://www.sololearn.com/learn/Java/2182/?ref=app
From set, you can directly take highest & lowest value after sorting it.
Happy coding

+ 6

You can generate all subsets along with sum of their elements, and then remove duplicate values of sum.
probably, a more better approach can be there, I will look for it.
For generating subsets in simple way, you can make use of binary.

+ 1

https://www.sololearn.com/Profile/6305872/?ref=app
Thank you for your answer:
"For generating subsets in simple way, you can make use of binary"
I have looked this up and tried using a binary mask. It is very useful.
If the sums contain duplicate values, it is not a valid set (for the algorithm I want).

+ 1

bell the example you provided (1, 2, 4) can be extended to any size with powers of 2.

+ 1

bell if you have a set of N elements then there are 2^N possible ways to sum them. Since you want all of them to be unique, you can't add any of these to the set while keeping the unique sum property. This will cause the set to contain large numbers even when N is small.

0

https://www.sololearn.com/Profile/3429252/?ref=app
you are right :-), I needed strings of similar lengths and powers of 2 grow too fast, while 1, 2 and 4 were too small. i have been playing with the code to generate such numbers. it might make a nice challenge (smallest set of N elements, lower sum limit 5)

0

https://www.sololearn.com/Profile/6305872/?ref=app
Thank you! I did not know there were sets in C++ but your lesson prompted me to look for them. In C++ they are even sorted by default! size will tell me if sums are unique but maybe there is a faster way of checking at insertion time to interrupt the moment duplication occurs.