# Unique magic triplets

## Description

Your input is a list of integers $$\[a_1, \dots, a_n]\$$.

A magic triplet is a triplet $$\(a_i, a_j, a_k)\$$ of values from this list, such that

• the indices $$\\{i, j, k\}\$$ are all distinct,
• the values are in ascending order ($$\a_i \leq a_j \leq a_k\$$), and
• the sum of two of the values equals the third.

Your task is to output all unique magic triplets, in any order.

## Rules

1. Each number in the input list is guaranteed to be in the range $$\-2^{32} \leq a < 2^{32}\$$.
2. The input list's length is guaranteed to be at most 1000.
3. The input list's length may be less than 3 (even 0). In this case, there are no magic triplets, and your program should produce an empty result.
4. The shortest answer in bytes wins.

## Test cases

[1,2,3,2,4] -> [[1,2,3], [1,3,4], [2,2,4]]
[0,0,0,0] -> [[0,0,0]]
[1,0,-1] -> [[-1,0,1]]
[1,2] -> []
[1,2,4,8,99] -> []
[33,90,7,24,60,32,80,43,15,40,36,90,65,12,91,33,88,1,96,33,40] -> [[7,33,40], [32,33,65], [1,32,33], [1,90,91], [7,36,43], [24,36,60], [12,24,36], [36,60,96], [15,65,80], [40,40,80]]


### Notes

• In the second test case, [[0,0,0], [0,0,0]] is not a valid answer. No triplet may be listed twice in the output.
• Remember that your program may order the triplets differently. For example, [[2,2,4], [1,2,3], [1,3,4]] is also a valid output for the first test case.
• Nonetheless, [[4,2,2], …] is invalid: each triplet itself must be in ascending order.
• Hey @chaugiang, I rewrote your question for clarity, and to be a bit more in the codegolf.SE “style”. If you disagree with my rewrite, feel free to roll it back (or fix what you dislike about it).
– Lynn
Nov 14 '19 at 16:43
• @Lynn Thank you a lot for your contributions. Nov 14 '19 at 23:53

# Ruby, 46 51 58 bytes

->l{l.permutation(3).select{|a,b,c|a+b==c}.map(&:sort)|[]}


Try it online!

Ok, not so straightforward, but now seems to work.

• I'm afraid this works only for input array already sorted ascending, which is not guaranteed by the challenge. For example from test case E it finds only 5 sets while 10 are expected. Nov 14 '19 at 10:02
• You are right. Fixed now.
– G B
Nov 14 '19 at 10:37
• Yepp, that was the easy fix. But handling negative numbers like in test case B [1, 0, -1] may be harder. ☹ Nov 14 '19 at 10:55
• Oops. Fixed again.
– G B
Nov 14 '19 at 11:05

# 05AB1E, 11109 10 bytes

{æ3ùêʒxsOå


+1 byte as bugfix for test cases like [1,0,-1] → [[-1,0,1]] (-1+1=0) and [-1,-2,-3] → [[-3,-2,-1]] (-1+-2=-3).

Explanation:

{           # Sort the (implicit) input-list from lowest to highest value
æ          # Take the powerset of this sorted list
3ù        # Only keep inner lists of length 3
ê       # (Sort and) uniquify this entire list of triplets
ʒ      # Filter this list of (individually sorted) triplets by:
x     #  Double each value in the triplet (without popping the triplet itself)
s    #  Swap to get the original triplet
O   #  Take the sum of this triplet
å  #  And check whether this value is in the doubled list
# (after which the filtered list is output implicitly as result)


The last four bytes could alternatively be œÆ0å (given by @Grimy): Try it online or verify all test cases.

      œ     #  Get all possible permutations of the triplet
Æ    #  Reduce each by subtracting: [a,b,c] → a-b-c
0å  #  And check if there are any 0s among the reduced permutations

• xsOå can also be œÆP>. Same byte-count, but more stylish. Nov 14 '19 at 13:55
• @Grimmy The Æ was also in my 9-byter. :) I've added it (with 0å instead of P>, since it's a bit more logical to me what's being checked). PS: It might be more stylish, but I think that permutations builtin would decrease the performance slightly, though. :) Nov 14 '19 at 14:03

# Jelly, 10 bytes

Ṣœc3ḤiSƊƇQ


Try it online!

Ṣ             Sort the input,
œc3          find all length-3 subsequences,
Ƈ     filter to only the sets for which
S       the sum of all three elements
i        is an element of
Ḥ  Ɗ      the set with all elements doubled,
Q    and uniquify.


# Brachylog, 11 bytes

{o⊇Ṫ.+/₂∈}ᵘ


Try it online!

Takes input through the input variable and outputs through the output variable.

{        }ᵘ    Output every unique output from:
.          the output is
⊇            a subsequence
Ṫ           of length 3
{              of the input
o             sorted
+         the sum of which
/₂       divided by 2
∈      is an element of
}     the output.

• [2,2,4] shouldn't be a magic triplet. I think you can fix by replacing the sort by distinct. Nov 15 '19 at 16:27
• The challenge spec only requires that the indices are distinct, and that the values within the triplet are non-decreasing (although it uses the word "increasing"). Note that the first test case contains two 2s and expects [2,2,4] to be output, and the fifth test case only contains one 2, so expects [2,2,4] to not be output. Nov 15 '19 at 22:40
• by bad, I didn't read the question properly. Nov 16 '19 at 11:58

# Japt, 13 11 bytes

á3 k_r-ÃmÍâ


Try it

á3 k_r-ÃmÍâ // input as arrays
á3            // all unique permutations
k_          // save list that..
r-Ã       // reduced by - from first element
mÍ   // ==mn   => sort all
â // remove duplicates


Thanks to @Shaggy and @Embodiment of Ignorance for saving 2

• 12 bytes: petershaggynoble.github.io/Japt-Interpreter/…. Using r- is very clever! Nov 14 '19 at 15:34
• 11 bytes Nov 14 '19 at 16:17
• @Embodiment of Ignorance thanks, it's been a while since I wanted to use it ! Forgot that sort can be just mn! Nov 14 '19 at 16:53
• Very nicely done, by the way. I took a quick, uncaffeinated stab at this this morning and ended up around 15 bytes. Nov 14 '19 at 23:21
• @Shaggy thanks for all the help given! Nov 15 '19 at 5:21

# Perl 6, 65 64 bytes

*.combinations(3)>>.sort.grep({@$_.sum==2*.any}).unique(:as(~*))  Try it online! *.combinations(3) # All the combinations of length 3 >>.sort # Sorted .grep({ }) # Filtered by {@$_.sum==         # The sum is equal to
2*.any   # Double any element
.unique(:as(~*))  # And take the unique lists

• Flooring the halved sum adds (0 0 1) to the new last test case ([0,0,0,0,1]). Nov 14 '19 at 7:51
• ...actually it adds a bunch of stuff to several test cases. I thought this might work as a fixed version, but 1. I don't actually know Perl and 2. it's missing (40 40 80) from the [33, 90, 7, 24, 60, 32, 80, 43, 15, 40, 36, 90, 65, 12, 91, 33, 88, 1, 96, 33, 40] case. Nov 14 '19 at 8:01
• @UnrelatedString Rolled back to a previous version. That test case was modified later (OP added the second 40), so I had the old version.
– Jo King
Nov 14 '19 at 8:04
• Ah, makes sense. Nov 14 '19 at 8:25

# JavaScript (Node.js),  118 116  115 bytes

Returns a set.

a=>new Set(a.flatMap((x,i)=>a.flatMap((y,j)=>j-i&&~(k=a.indexOf(x+y))&&k-i&&k-j?[x,y,x+y].sort((a,b)=>a-b)+'':[])))


Try it online!

### Commented

a =>                             // a[] = input array
new Set(                       // create a set:
a.flatMap((x, i) =>          //   for each value x at position i in a[]:
a.flatMap((y, j) =>        //     for each value y at position j in a[]:
j - i &&                 //       if j is not equal to i
~(                       //       and the position k
k = a.indexOf(x + y)   //       of x + y in a[]
) &&                     //       is not equal to -1
k - i &&                 //       and k is not equal to i
k - j ?                  //       and k is not equal to j:
[x, y, x + y]          //         build the triplet (x, y, x + y)
.sort((a, b) => a - b) //         sort it in ascending order
+ ''                   //         and coerce it to a string
:                        //       else:
[]                     //         yield an empty array
)                          //     end of inner flatMap()
)                            //   end of outer flatMap()
)                              // end of Set()


# Python 3, 94, 89, 88, 85 bytes

One byte saved thanks to frank.

lambda l:{p for p in combinations(sorted(l),3)if sum(p)/2in p}
from itertools import*


Try it online!

import Data.List
f x=nub[y|y@[a,b,c]<-subsequences\$sort x,or[2*z==sum y|z<-y]]


Try it online!

# K (oK), 38 bytes

{?{x@<x}'({z=x+y}.)#x@/:{x~?x}#+!3##x}


Try it online!

# Charcoal, 66 bytes

ＦＬθＦＬθＦＬθＦ¬⌈⟦⁼ικ⁼ιλ⁼κλ›§θι§θκ›§θκ§θλ⟧«≔Ｅ⟦ικλ⟧§θνη¿∧№η⊘Ση¬№υη⊞υη»Ｉυ


Try it online! Link is to verbose version of code. Explanation:

ＦＬθＦＬθＦＬθＦ¬⌈⟦


Loop through all triples of indices...

⁼ικ⁼ιλ⁼κλ


... checking whether the indices are distinct...

›§θι§θκ›§θκ§θλ


... and that the triplet is in ascending order...

⟧«≔Ｅ⟦ικλ⟧§θνη


... if so then save the triplet in a variable...

¿∧№η⊘Ση¬№υη⊞υη


... and if it contains its halved sum and is unique then remember it in a list.

»Ｉυ


After checking all triplets output the unique magic triplets double-spaced with each triplet member on its own line.

# Java 10, 225 bytes

import java.util.*;L->{var r=new TreeSet();for(int j,k,a,b,t[],i=L.size();i-->0;)for(j=i;j-->0;)if((k=L.indexOf((a=L.get(i))+(b=L.get(j))))>=0&k!=i&k!=j){Arrays.sort(t=new int[]{a,b,a+b});r.add(Arrays.toString(t));}return r;}


Port of @Arnauld's JavaScript answer, just twice as long.. >.>

Try it online.

Explanation:

import java.util.*;       // Required import for the TreeSet and both Arrays
L->{                      // Method with integer-List as parameter & sorted Set as return
var r=new TreeSet();    //  Result-set, starting uninitialized
//  A Set will automatically remove duplicates
//  (and a TreeSet will automatically sort, which is irrelevant,
//   but it's the same size as a regular HashSet anyway)
for(int j,k,a,b,t[],    //  Temp integers
i=L.sisze();i-->0;) //  Loop i in the range (input-length, 0]:
for(j=i;j-->0;)       //   Inner loop j in the range (i, 0]:
if((k=L.indexOf((a=L.get(i))
//    Set a to the i'th value in the list
+(b=L.get(j))   //    Set b to the j'th value in the list
//    And add a and b together
))               //    Set k to the index of this sum
>=0            //    If the index k is NOT -1
&k!=i&k!=j){     //    And k is also NOT i nor j:
Arrays.sort(t=new int[]{a,b,a+b});
//     Create an array t with items [a,b,a+b],
//     and sort the values of this triplet
//     Then convert this array to a String,
//     and add it to the result-TreeSet
return r;}              //  After the nested loop: return the result-TreeSet


# Pyth, 13 bytes

{f}csT2T.cSQ3


Try it online!

Port of the solution thats been floating around.

## How it works

{f}csT2T.cSQ3
.c  3  - All combinations length 3 of...
SQ   - The sorted input
f             - Filtered such that...
csT2        - Half the sum of each combination...
}    T       - Is an element of the original combination
{              - Remove duplicates


# Pyth, 15 bytes

{mSdfqsPTeT.PQ3


Try it online!

Less sophisticated solution. Posting it because I think it can be golfed more

## How it works

{mSdfqsPTeT.PQ3
.PQ3 - All 3 element permutations of the input
f           - Filtered such that
sPT       - The sum of the first 2 inputs...
q   eT     - Is equal to the last input
mSd            - Sort all elements
{               - Remove duplicates


### JULIA

A solution w/o external package:

F(l)=(n=length(sort!(l));a=Set();
for i=1:n,j=1:n,k=1:n i<j<k&&(v=l[[i,j,k]];sum(v) in 2v)&&push!(a,v)end;
[a...])


Not a nice one 115 bytes of code (with 2 extra newlines for readability).

A solution using the non-core package Combinatorics:

using Combinatorics
H(l)=[Set(v for v in combinations(sort(l),3) if sum(v) in 2v)...]


Length 85 bytes (or 84 if you omit the space before the '''if''')
You can REPLIT online.

• Welcome to CG&CC! I tried running your solution online, but the Combinatorics package doesn't seem to be installed on TIO. I don't think there's any problem with using non-standard libraries so long as you mention them in the language header, but it might be a good idea to also write a solution that can be more easily verified. Nov 16 '19 at 9:21