N-uniquely additive sets

Question

Remember that a set is unordered without duplicates.

Definition An N-uniquely additive set S whose length is K is a set such that all N-length subsets in S sum to different numbers. In other words, the sums of all the N-length subsets of S are all distinct.

Objective Given an array/set as input and a number N to a function or to a full program in any reasonable format, find and return or output a truthy or falsey value (erroring for falsey is okay) denoting whether or not the input is N-uniquely additive.

You may assume that each element only appears at most once and that each number is within your language's native datatype. If need be, you may also assume that the input is sorted. Last, you may assume that 0 < N <= K.

Examples

Let's consider the set S = {1, 2, 3, 5} and N = 2. Here are all the sums of all unique pairs over S (for the unique ones are the only ones of interest for sums):

1 + 2 = 3
1 + 3 = 4
1 + 5 = 6
2 + 3 = 5
2 + 5 = 7
3 + 5 = 8

We can see that there are no duplicates in output, so S is 2-uniquely additive.

---

Let's now consider the set T = {12, 17, 44, 80, 82, 90} and N = 4. Here are all the possible sums of length four:

12 + 17 + 44 + 80 = 153
12 + 17 + 44 + 82 = 155
12 + 17 + 44 + 90 = 163
12 + 17 + 80 + 82 = 191
12 + 17 + 80 + 90 = 199
12 + 17 + 82 + 90 = 201
12 + 44 + 80 + 82 = 218
12 + 44 + 80 + 90 = 226
12 + 44 + 82 + 90 = 228
12 + 80 + 82 + 90 = 264
17 + 44 + 80 + 82 = 223
17 + 44 + 80 + 90 = 231
17 + 44 + 82 + 90 = 233
17 + 80 + 82 + 90 = 269
44 + 80 + 82 + 90 = 296

They are all unique, and so T is 4-uniquely additive.

Test Cases

[members], N => output
[1, 4, 8], 1 => true
[1, 10, 42], 1 => true                ; all sets trivially satisfy N = 1
[1, 2, 3, 4], 3 => true
[1, 2, 3, 4, 5], 5 => true
[1, 2, 3, 5, 8], 3 => true
[1, 2, 3, 4, 5], 2 => false           ;  1 +  4       =  5 =        2 + 3
[-2, -1, 0, 1, 2], 3 => false         ; -2 + -1 + 2   = -1 =   -2 + 0 + 1
[1, 2, 3, 5, 8, 13], 3 => false       ;  1 +  2 + 13  = 16 =    3 + 5 + 8
[1, 2, 4, 8, 16, 32], 3 => true
[1, 2, 4, 8, 16, 32], 4 => true
[1, 2, 4, 8, 16, 32], 5 => true
[1, 2, 4, 8, 16, 32], 6 => true
[3, 4, 7, 9, 12, 16, 18], 6 => true
[3, 4, 7, 9, 12, 16, 18], 3 => false  ; 3 + 4 + 12 = 19 = 3 + 7 + 9

Answer 1

MATL, 7 bytes

XN!sSdA

Try it online!

Returns true (displayed as 1) or false (displayed as 0).

XN   % Take array S and number N. Generate all combinations of elements from S 
     % taken N at a time. Gives a 2D array where each combination is a row
!    % Transpose. Each combination is now a column
s    % Sum of each column: gives a row array. If N=1 computes the sum of
     % the only row, and so gives a number
S    % Sort vector
d    % Array of consecutive differences. For a single number gives an empty array
A    % True if all elements of the input array are nonzero (for an empty array
     % it also gives true)

Answer 2

Jelly, 7 bytes

œcS€ṢIP

Try it online!

Returns a positive number for truthy and zero for falsey.

œc       find combinations
  S€     sum each combination
    Ṣ    sort the sums
     I   find the difference between each pair of sums 
           iff any sums are the same, this returns a list containing 0
      P  product of the elements of the resulting list

Answer 3

Matlab, 78 bytes

function n=f(s,n);p=perms(s);k=sum(unique(sort(p(:,1:n)),'rows')');unique(k)-k

This function returns a positive value (in fact n) for truthy and returns an error as a falsey answer (valid according to this comment)

Explanation:

function n=f(s,n);
p=perms(s); %create all permutations of the set

k=sum(unique(sort(p(:,1:n)),'rows')');
                  %just take the first n entries of each permutation
             %sort those entries and
      %filter out all duplicates (we sorted as the order should NOT matter)
  %then sum each of those candidates

unique(k)-k
%if all those sums are distinct, unique(k) will have the same size 
% as k itself, and therefore we can subtract, otherwise it will throw 
% an error as we try to subtract vectors of different sizes

Answer 4

Pyth, 8 bytes

{IsM.cFQ

Test suite.

       Q   eval input (provided as a 2-element array)
    .cF    splat over combination
  sM       sum each combination
{I         is the result invariant under { (dedup/uniq)?

Answer 5

Haskell, 69 bytes

import Data.List
n#s=(==)=<<nub$[sum x|x<-subsequences s,length x==n]

Usage example: 6 # [3,4,7,9,12,16,18] -> True.

Direct implementation of the definition: make a list of sums of all subsequences of length n and check if it equals itself with duplicates removed.

Answer 6

JavaScript (ES6), 132 bytes

(a,n)=>a.map(m=>{for(i=n;i--;)s[i].map(k=>s[i+1].push(m+k))},s=[...Array(n+1)].map(_=>[]),s[0]=[0])&&new Set(s[n]).size==s[n].length

Builds up the additive lists from 1 to n and then checks the last one for uniqueness.

Answer 7

Julia, 46 41 bytes

x\n=(t=map(sum,combinations(x,n)))==t∪t

Try it online!

How it works

This (re)defines the binary operator \ for Array/Int arguments.

combinations(x,n) returns all arrays of exactly n different elements of x. We map sum over these arrays and store the result in t.

t∪t performs the set union of the array t with itself, which works like the longer unique in this case.

Finally, we compare t with the deduplicated t, returning true if and only if all sums are different.

Answer 8

Python, 89 bytes

from itertools import*
lambda s,n,c=combinations:all(x^y for x,y in c(map(sum,c(s,n)),2))

Test it on Ideone.

How it works

c(s,n) lists all n-combinations of s, i.e., all lists of n different elements of s. We map sum over the resulting lists, thus computing all possible sums of sublists of length n.

After wards, we use c(...,2) to create all pairs of the resulting sums. If any two sums x and y are equal, x^y will return 0 and all will return False. Conversely, if all sums are unique, x^y will always be truthy, and any will return True.

Answer 9

Brachylog, 20 bytes

:1f:+aLdL
[L:I]hs.lI

Expects a list containing the list and then the integer as Input, and no Output, e.g. run_from_atom(':{[L:I]hs.lI}f:+aLdL', [[1:2:3:5]:2])..

Explanation

• Main Predicate

             Input = [A:I]
  :1f        Find all ordered subsets of A of length I
     :+aL    Apply summing to each element of that list of subsets. Call that L
         dL  True if L minus all duplicate elements is still L
  

• Predicate 1: Find all ordered subsets of fixed length of a list

  [L:I]      Input = [L:I]
       hs.   Unify Output with an ordered subset of L
          lI True if I is the length of Output
  

Answer 10

J, 34 bytes

load'stats'
[:*/@~:[:+/"1(comb#){]

Straight-forward approach, only requires the stats add-on for the comb function. Returns 0 for false and 1 for true.

As an alternative to using the comb builtin, there is a 38 byte solution that generates the power set and chooses the subsets of size n.

[:*/@~:(>@{[:(</.~+/"1)2#:@i.@^#)+/@#]

Usage

   f =: [:*/@~:[:+/"1(comb#){]
   2 f 1 2 3 5
1
   4 f 12 17 44 80 82 90
1
   3 f _2 _1 0 1 2
0
   6 f 3 4 7 9 12 16 18
1
   3 f 3 4 7 9 12 16 18
0

Answer 11

Ruby, 50 bytes

->s,n{!s.combination(n).map{|c|c.inject :+}.uniq!}

Try it online!

If all elements are unique, uniq! returns nil. Negating that result, as in !(...).uniq! makes for a nice uniqueness test.

This question was posted a few weeks before Ruby 2.4.0-preview1, which introduced Enumerable#sum, which would save 9 bytes here.

41 bytes (Ruby 2.4+)

->s,n{!s.combination(n).map(&:sum).uniq!}

Try it online!

Answer 12

R, 41 bytes

function(s,n)max(table(combn(s,n,sum)))<2

Sums all n-length subsets of s and checks if all values in a contingency table of these sums are 1 (all sums are unique).

Try it online!