5
\$\begingroup\$

Inspiration: Leetcode's [3Sum] link

Problem

Given an array nums of n (not necessarily distinct) integers, and given a target number target, return an array of all of the unique quintuplets [nums[a],nums[b],nums[c],nums[d],nums[e]] such that the following conditions are held:

  1. 0 <= a,b,c,d,e < n (or 1 <= a,b,c,d,e <= n if using 1-indexing)
  2. All of a,b,c,d,e are distinct.
  3. nums[a] + nums[b] + nums[c] + nums[d] + nums[e] = target
    • In the case of multiple arrays, we also add the requirements that at least two values in each of the arrays are distinct.

If all 3 conditions cannot be satisfied, you can return a junk value of your liking, or just an empty array [[]]. The testcases down below will use -1 as the specified junk value.

You may return the answer in any order. For example, given the array [-5,-2,-2,1,3,4,6] and target 0, you could return any permutation of [[-5,-2,-2,3,6]]. You do not need to return all possible permutations of one single array.

Testcases:

# Note: Thank you all for the additional test cases! However,
#       I will not be taking any more at this time just so the
#       question doesn't appear on the [Home] page for too long.

 Array: [-5,-2,-2,1,3,4,6]
Target: 0
Output: [[-5,-2,-2,3,6]]

 Array: [-5,-4,-2,0,1,2,6]
Target: 1
Output: [[-5,-2,0,2,6],[-4,-2,0,1,6]]

# Note that outputting `[[-4,-2,0,1,6],[-5,-2,0,2,6]]` is also valid,
# although returning just `[[-4,-2,0,1,6]]` or `[[-5,-2,0,2,6]]` is not.

 Array: [0,-1,2,3]
Target: 4
Output: -1

 Array: [0,1,-9,6,7]
Target: 6
Output: -1

 Array: [0,1,9,9,5]
Target: 45
Output: -1

 Array: [1,4,6,9,-4]
Target: 16
Output: [[1,4,6,9,-4]]

 Array: [1,0,9,6,5,0]
Target: 21
Output: [[1,0,9,6,5]]

 Array: [1,0,9,6,5,4,7]
Target: 21
Output: [[1,0,9,6,5],[1,0,9,4,7]]

 Array: [1,0,9,6,5,4,4,7]
Target: 21
Output: [[1,0,9,6,5],[1,0,9,4,7],[0,6,4,4,7],[1,5,4,4,7]]

# Above test case suggested by @Shaggy

 Array: [1,1,2,2,3,3,4,4]
Target: 11
Output: [[1,2,2,3,3],[1,1,2,3,4]]

# Above test case suggested by @Arnauld

This is , so the shortest solution wins!

Improve this question
\$\endgroup\$
7
  • \$\begingroup\$ Suggested test case: [1,0,9,6,5,4,4,7], 21. \$\endgroup\$
    – Shaggy
    Commented 13 hours ago
  • \$\begingroup\$ @Shaggy Added . \$\endgroup\$
    – CrSb0001
    Commented 13 hours ago
  • \$\begingroup\$ What's the source for this problem? \$\endgroup\$
    – xnor
    Commented 13 hours ago
  • \$\begingroup\$ @xnor Sorry, should've added that. My inspiration for this was from Leetcode's "3Sum" problem. \$\endgroup\$
    – CrSb0001
    Commented 13 hours ago
  • \$\begingroup\$ shouldn't the last test case be [[1,0,9,6,5],[1,0,9,4,7],[0,6,4,4,7],[1,5,4,4,7]]? all of the current answers (and mine) return that. \$\endgroup\$
    – nyxbird
    Commented 12 hours ago

10 Answers 10

Reset to default
2
\$\begingroup\$

Vyxal, 20 bytes

→tṖƛ5Þİ_;'∑←t=;λsS;ε

First Vyxal submission 🎉 Almost certainly golf-able.

Explained

→t                      # Assign the target to t
  Ṗ                     # Get all permutations of the input list
   ƛ5Þİ_;               # Taking the first 5 elements of each permutation
         '∑←t=;         # Where the sum is equal to t
               λsS;ε    # Uniqueify by the sorted string

Try it Online!

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Vyxal, 8 bytes

s5ḋU'∑⁰=

Try it Online!

-2 from emanresu

Takes list then target.

Explained

s5ḋU'∑⁰=­⁡​‎‎⁡⁠⁡‏‏​⁡⁠⁡‌⁢​‎‎⁡⁠⁢‏⁠‎⁡⁠⁣‏‏​⁡⁠⁡‌⁣​‎‎⁡⁠⁤‏‏​⁡⁠⁡‌⁤​‎‎⁡⁠⁢⁡‏‏​⁡⁠⁡‌⁢⁡​‎‎⁡⁠⁢⁢‏⁠‎⁡⁠⁢⁤‏‏​⁡⁠⁡‌⁢⁢​‎‎⁡⁠⁢⁣‏‏​⁡⁠⁡‌­
s         # ‎⁡Sort the input. This helps with uniquification later
 5ḋ       # ‎⁢Get all combinations without replacement of length 5
   U      # ‎⁣Filter out duplicate instances of combinations
    '     # ‎⁤Keep combinations where:
     ∑ =  # ‎⁢⁡  The sum equals
      ⁰   # ‎⁢⁢  The target
💎

Created with the help of Luminespire.

Improve this answer
\$\endgroup\$
4
  • \$\begingroup\$ @Arnauld I allow it to be 0-indexed or 1-indexed. \$\endgroup\$
    – CrSb0001
    Commented 12 hours ago
  • \$\begingroup\$ @Arnauld I don't see why it wouldn't, regardless of 0 or 1 indexing. \$\endgroup\$
    – lyxal
    Commented 11 hours ago
  • 1
    \$\begingroup\$ @Arnauld "You may return the answer in any order. For example, given the array [-5,-2,-2,1,3,4,6] and target 0, you could return any permutation of [[-5,-2,-2,3,6]]." \$\endgroup\$
    – lyxal
    Commented 11 hours ago
  • \$\begingroup\$ My bad. I was reading the 1st condition as 0 <= a<b<c<d<e < n from the beginning. \$\endgroup\$
    – Arnauld
    Commented 3 hours ago
2
\$\begingroup\$

Uiua, 11 bytes

◴▽=⤚≡/+⧅<5⍆

Try it!

◴▽=⤚≡/+⧅<5⍆
           ⍆ # sort
        ⧅<5   # get quintuples
 ▽=⤚≡/+       # keep those for which the sum equals the target
◴             # and deduplicate
Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Charcoal, 57 bytes

Ｗ⁻θυＦ№θ⌊ι⊞υ⌊ι≔⟦⟧θＦＥＸ²ＬυＥ⌕Ａ⮌⍘ι²1§υλＦ⁼⁵ＬιＦ⁼ηΣιＦ¬№θι⊞θιＥθ⭆¹ι

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

Ｗ⁻θυＦ№θ⌊ι⊞υ⌊ι

Sort the input list.

≔⟦⟧θ

Start with no results.

ＦＥＸ²ＬυＥ⌕Ａ⮌⍘ι²1§υλ

Get all subsets of the sorted list.

Ｆ⁼⁵Ｌι

Filter on those that have length 5.

Ｆ⁼ηΣι

Filter on those with the desired total.

Ｆ¬№θι

Filter on those that are distinct.

⊞θι

Keep only the distinct subsets of 5 with the correct total.

Ｅθ⭆¹ι

Pretty-print the found subsets.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

Python 3, 95 bytes

f=lambda t,a,*p:[p][t*t:len(p)==5]or{i for v in[*a]for i in f(t-a.pop(0),[*a],*sorted([*p,v]))}

Try it online!

Input target value and the array of nums, output a set of tuples.

Improve this answer
\$\endgroup\$
2
\$\begingroup\$

JavaScript (V8), 92 bytes

f=([c,...x],s,n=R=[])=>1/n[4]?s||R[n.sort()]||print(R[n]=n):1/c?f(x,s,n)^f(x,s-c,[...n,c]):x

Try it online!

JavaScript (Node.js), 97 bytes

f=([c,...x],s,n=R=[])=>1/n[4]?s||R[n.sort()]?[]:[R[n]=n]:1/c?[...f(x,s,n),...f(x,s-c,[...n,c])]:x

Try it online!

JavaScript (Node.js), 98 bytes

f=(x,s,i=R={},...n)=>1/n[4]?s||R[n.sort()]?[]:[R[n]=n]:x.flatMap((e,j)=>i<=j?[]:f(x,s-e,j,...n,e))

Try it online!

Dedup

Improve this answer
\$\endgroup\$
1
  • \$\begingroup\$ f=([c,...x],s,n=R=[])=>1/n[4]?R[n.sort()]??=s||+print(n):1/c?f(x,s,n)^f(x,s-c,[...n,c]):x \$\endgroup\$
    – tsh
    Commented 1 hour ago
2
\$\begingroup\$

Japt, 12 bytes

Outputs an empty array if no solution is possible.

Íà5 â fÈx ¶V

Try it

Íà5 â fÈx ¶V     :Implicit input of array U & target integer V
Í                :Sort U
 à5              :Combinations of length 5
    â            :Deduplicate
      f          :Filter by
       È         :Passing through the following function
        x        :  Reduce by addition
          ¶V     :  Equal to V?
Improve this answer
\$\endgroup\$
2
  • \$\begingroup\$ Why doesn't Í pop up in the 'Search method' in the online compiler? I searched for sort and it didn't pop up, and even if I search directly for Í, only the lowercase versions pop up. 🤔 (Hence why I mentioned ñ as sort instead.) \$\endgroup\$
    – Kevin Cruijssen
    Commented 1 hour ago
  • \$\begingroup\$ @KevinCruijssen, Í is a (shortcut)[petershaggynoble.github.io/Japt-Interpreter/… for n2<space>. It's primary intent is for use on strings, where the n method converts to an integer and the 2 argument specifies from binary. The n method when used on an array, though, sorts the array and the 2 is ignored as the method doesn't expect an integer as an argument. \$\endgroup\$
    – Shaggy
    Commented 1 hour ago
1
\$\begingroup\$

Python 3, 755 bytes

def fiveSum (nums,target):
    nums.sort()
    s=[]
    for i in range(len(nums)-4):
        if i>0 and nums[i]==nums[i-1]:
            continue
        for j in range(i+1,len(nums)-3):
            for k in range(j+1,len(nums)-2):
                l,m=k+1,len(nums)-1
                while l<m:
                    a=nums[i]+nums[j]+nums[k]+nums[l]+nums[m]
                    if a<target:
                        l+=1
                    elif a>target:
                        m-=1
                    else:
                        s.append((nums[i],nums[j],nums[k],nums[l],nums[m]))
                        l+=1
                        while nums[l]==nums[l-1] and l<m:
                            l+=1
    k=[]
    for b in list(set(s)):
        k.append(list(b))
    return k

Explanation:

def fiveSum (nums,target):
    nums.sort()                                                             # does NOT return all 4 solutions for the last case if removed, unsure why
    s=[]                                                                    # ^ (only returns two/four arrays)
    for i in range(len(nums)-4):                                            # i < j < k < l < m
        if i>0 and nums[i]==nums[i-1]:                                      # later loops will cover all of the
            continue                                                        # other cases, so no need to recurse through them again
        for j in range(i+1,len(nums)-3):                                    # for j in range
            for k in range(j+1,len(nums)-2):                                # for k in range
                l,m=k+1,len(nums)-1                                         # No more "_ in range" needed anymore
                while l<m:                                                  # i < j < k < l < m
                    a=nums[i]+nums[j]+nums[k]+nums[l]+nums[m]               # The sum
                    if a<target:                                            # check if nums[0]+nums[1]+...+nums[4] == target
                        l+=1                                                # it probably doesn't, so increment l by 1
                    elif a>target:                                          # if overshoot
                        m-=1                                                # if it does, decrement m by 1
                    else:
                        s.append((nums[i],nums[j],nums[k],nums[l],nums[m])) # append to list
                        l+=1
                        while nums[l]==nums[l-1] and l<m:                   # More incrementation! (Yay?)
                            l+=1
    k=[]                                                                    # The final list
    for b in list(set(s)):
        k.append(list(b))
    return k                                                                # return List[List[str]]
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

05AB1E, 8 bytes

{5.ÆÙʒOQ

Inputs in the order \$array,target\$. Outputs [] if there is no valid result.

Try it online or verify all test cases.

Explanation:

{         # Sort the first (implicit) input-list
 5.Æ      # Get all 5-element combinations of this list
    Ù     # Uniquify this list of quintuplets
     ʒ    # Filter it by:
      O   #  Where the sum of the quintuplet
       Q  #  Equals the second (implicit) input-integer
          # (after which the result is output implicitly)
Improve this answer
\$\endgroup\$
0
\$\begingroup\$

JavaScript (V8), 94 bytes

f=([v,...a],n,o=q=[])=>1/v?f(a,n-v,[...o,v])|f(a,n,o):n|o.sort().length-5||q[o]||print(q[o]=o)

Try it online!

Commented

f = (             // f is a recursive function taking:
  [v,             //   v = next value from the input array
      ...a],      //   a[] = remaining values
  n,              //   n = target sum
  o =             //   o[] = current output array
  q = []          //   q = object to keep track of output arrays
) =>              //
1 / v ?           // if v is defined:
  f(              //   1st recursive call:
    a,            //     pass a[]
    n - v,        //     subtract v from n
    [...o, v]     //     append v to o[]
  ) |             //   end of recursive call
  f(a, n, o)      //   2nd recursive call with everything unchanged
:                 // else:
  n |             //   if n is not 0
  o.sort()        //   or o[], which is sorted here,
  .length - 5 ||  //   has not a length of 5
  q[o] ||         //   or q[o] is already set, then do nothing
  print(q[o] = o) //   otherwise, print o[] and set q[o]
Improve this answer
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.