Largest Distinctly Sum-Free Partition

Question

_{related and inspired by -- Finding sum-free partitions}

A set A is defined here as being distinctly sum-free if

• 1) it consists of at least three elements, |A| ≥ 3, and
• 2) its distinct self-sum A + A = { x + y | x, y in A} (with x,y distinct, i.e., x≠y) has no elements in common with A.

_{(Obsolete - do not use this going forward. Left here only because some answers may have used it. It does not match with the above conditions. Alternatively, the equation x + y = z has no solution for x,y,z ∈ A (again with x,y,z distinct, i.e., x≠y, x≠z, y≠z).)}

For a simple example, {1,3,5} is distinctly sum-free, but {1,3,4} is not. {1,3} and {3} are also not, since they're not at least three elements.

The challenge here is to find the largest distinctly sum-free subset of the given input.

Input

• An unordered set A of integers in any convenient format.
• The integers could be positive, negative, or zero, but can be assumed to fit in your language's native [int] datatype (or equivalent).
• The set is guaranteed to have only distinct elements (no multisets here).
• The set is not necessarily sorted.

Output

• The largest subset of A (which could be A itself), that is distinctly sum-free. Output can be in any suitable format.
• If no such subset exists, output an empty set or other falsey value.
• If multiple subsets are tied for largest, output any or all of them.
• The subset does not necessarily need be sorted, or in the same order as the input. For example, for input {1,3,5} output {5,1,3} is acceptable.

Additional Rules

• Standard loopholes are forbidden.
• This is code-golf, so all usual golfing rules apply, and the shortest code wins.

Examples

Input     -> Output (any or all)
{0}       -> {}
{1, 2, 3} -> {}
{1, 3, 5} -> {1, 3, 5}
{1, 2, 3, 4, 5} -> {1, 2, 5}  {1, 2, 4}  {1, 3, 5}  {2, 3, 4}  {2, 4, 5}  {3, 4, 5}
{-5, 4, 3, -2, 0} -> {-5, 4, 3}  {-5, 4, -2}  {4, 3, -2}
{-5, 4, 3, -2} -> {-5, 4, 3}  {-5, 4, -2}  {4, 3, -2}
{-17, 22, -5, 13, 200, -1, 1, 9} -> {-17, 22, -5, 13, 200, -1, 1}  {-17, 22, -5, 200, -1, 1, 9}  {-17, -5, 13, 200, -1, 1, 9}

Answer 1

MATL, 47 43 bytes

nW:qB!ts2#Sw2>)PZ)"1G@)XJ2XN!"@sJ@X-m~*]?J.

Try it online!

Explanation

This uses two loops: an outer loop to generate all possible subsets, and an inner loop to take all pairs of elements and see if the sum equals any other element of the subset.

Subsets of at least 3 elements are tested in order of decreasing number of elements. The code stops as soon as a valid subset is found.

          % Take input implicitly
nW:q      % Generate [0 1 ... 2^n-1] where n is input length
B!        % Convert to binary. Gives a matrix. Each number corresponds to a column.
          % This will be used to select the elements of each subset
ts        % Duplicate. Sum of each column
2#S       % Sort. Output the sorted array and the indices of the sorting. Each index
          % corresponds to one possible subset
w2>       % Swap. Logical index of values that exceed 2. This is used to pick only
          % subsets of more than 2 elements
)         % Keeps only indices of subsets that have at least 3 elements
P         % Flip. This moves subsets with more elements to the front. As soon as a
          % subset fulfills the condition the outer loop will be exited, so we need
          % to start with the bigger subsets
Z)        % Index into columns of binary matrix. Each column is the binary pattern
          % defining a subset with at least 3 elements, starting with bigger subsets
"         % For each column. Each iteration corresponds to a subset
  1       %   Push 1
  G@)     %   Pick actual elements of each subset (logical index into input)
  XJ      %   Copy to clipboard J
  2XN!    %   All pairs of 2 elements from that subset. Each pair is a column
  "       %   For each column. Each iteration corresponds to a pair of elements
    @s    %     Sum of those two elements
    J@X-  %     Array with the other elements (obtained with set difference)
    m~    %     True if the sum of the two elemens is not a member of the array
    *     %     Multiply. Corresponds to logical AND
  ]       %   End for
  ?       %   If result is true: no sum of two elements equalled any element
    J     %     Push found subset (will be displayed implicitly)
    .     %     Exit loop
          %   End if implicitly
          % End for implicitly
          % Display stack implicitly

Answer 2

Python, 137 bytes

A naïve approach. Loops over all subsets of the input containing at least 3 values, checking the property for each one. Returns [] when no result is found or [S] if at least one result is found (where S is some tuple).

from itertools import*
lambda a:[c for n in range(3,len(a)+1)for c in combinations(a,n)if all(x+y-z for(x,y,z)in permutations(c,3))][-1:]

Answer 3

Javascript 246 263

a=>([...Array(1<<(l=a.length))].map((x,i)=>i.toString(2)).filter(n=>/1.*1.*1/.test(n)).map(s=>('0'.repeat(l)+s).slice(-l).replace(/./g,(b,p)=>+b&&o.push(a[p]),o=[])&&o).filter(u=>u.every((x,i)=>!u.some((y,j)=>j-i&&u.some((z,k)=>k-j&&!(z-x-y))))))

So long :( ... But it was a nice coding ..(I think)

Less golfed:

f=a=>(
    [...Array(1<<(l=a.length))]
        .map((x,i)=>i.toString(2))
        .filter(n=>/1.*1.*1/.test(n))
        .map(s=>
            ('0'.repeat(l)+s).slice(-l).replace(/./g,
                (b,p)=>+b&&o.push(a[p])
            ,o=[])&&o
        )
        .filter(u=>
            u.every((x,i)=>
                !u.some((y,j)=>
                    j-i&&u.some((z,k)=>k-j&&!(z-x-y))
                )
            )
        )
)

document.body.innerHTML = JSON.stringify( f([1,2,3,4,5]), null, 1 );

Answer 4

Mathematica - 89 84 83 77 76 bytes

6 bytes saved thanks to @Sp3000

Probably can be golfed a lot more, is there a shorter way to filter?

Select[Subsets@#,Length@#>2&&Intersection[#,Tr/@#~Subsets~{2}]=={}&]~Last~0&

Anonymous function, returns 0 on no answer.

Answer 5

Ruby, 107 bytes

Input is an array. Collects one qualifying subset for each subset size from 3 to the input length, then returns the biggest one out of the ones found. Returns nil if no result is found.

Because of the conflicting spec, there are two solutions that currently have the same bytecount.

Using the first definition: ({ x + y | x, y ∈ A } ∩ A = ∅)

->s{((3..s.size).map{|i|s.combination(i).find{|e|e.combination(2).map{|a,b|a+b}&e==[]}}-[p])[-1]}

Using the second definition (∀ x, y, z ∈ A: x + y ≠ z)

->s{((3..s.size).map{|i|s.combination(i).find{|e|e.permutation(3).all?{|a,b,c|a+b!=c}}}-[p])[-1]}

Answer 6

Jelly, 17 bytes

8BḊ+œc2S€f
ŒPÇÐḟṪ

Try it online! or verify all test cases.

Answer 7

Pyth, 27 bytes

ef!f!*Fm-Fd.pYfqlY3yTfglT3y

Test suite.