Monday, January 9, 2023

Sets with distinct subset sums

So I encountered a problem at work today that I thought was interesting.

It's this: generate a set of size n of integers, such that every subset of the set has a distinct sum. This way, given a sum you can know unambiguously which subset of integers of that set were added together to create that sum.

For example, [1,2,4] has this property: given any sum, you know which subset of [1,2,4] were added to create that sum.

The set [1,1,1] does not have this property: given the sum 1, you don't know which element created that sum.

The set [1,2,3] does not have this property: given the sum 3, it could be the sum of [1,2] or it could be the sum of [3]. So you can't tell unambiguously which subset was added up to get that sum.