Skip to main content
5 of 5
added 322 characters in body
CrSb0001
  • 489
  • 2
  • 14

Find all unique quintuplets in an array that sum to a given target

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!

CrSb0001
  • 489
  • 2
  • 14