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

Post

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

−0

^{Inspiration: Leetcode's [3Sum] link
Link on CG&CC}

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:

0 <= a,b,c,d,e < n (or 1 <= a,b,c,d,e <= n if using 1-indexing)

All of a,b,c,d,e are distinct.

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 [[]] or []. 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:

 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]]

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

 Array: [-1,1,1,1,1,1,3]
Target: 5
Output: [[1,1,1,1,1],[-1,1,1,1,3]]

# Above test case suggested by @trichoplax

This is [code-golf], so the shortest solution wins!

code-golf array arithmetic

posted about 1 month ago

CC BY-SA 4.0

1mo ago

CrSb0001‭

11 reputation 4 1 2 5

Raw

Markdown

History

is a duplicate

This question has been asked before and has already been answered. It should be marked as a duplicate.

Please enter the URL of the proposed duplicate in the details field below.

not constructive

This question cannot be answered in a way that is helpful to anyone. It's not possible to learn something from possible answers, except for the solution for the specific problem of the asker.

−0

Japt, 12 bytes Outputs an e …

1mo ago

1 comment thread

Clarification of arrays (9 comments)

trichoplax‭ wrote about 1 month ago

copy link

In the case of multiple arrays, we also add the requirements that at least two values in each of the arrays are distinct.

Does this mean "for each pair of quintuplets, each quintuplet must have at least 2 elements not present in the other", or the stronger "for each quintuplet, at least 2 of its elements must be present in no other quintuplet", or something else?

trichoplax‭ wrote about 1 month ago · edited about 1 month ago

copy link

In addition to editing to make the correct interpretation explicit, it would be helpful to have some test cases for this specific situation.

For example, what should be the output for the following input:

-1, 1, 1, 1, 1, 1, 3
Target: 5

trichoplax‭ wrote about 1 month ago · edited about 1 month ago

copy link

You do not need to return all possible permutations of one single array.

Does this mean that you are permitted to return only one permutation of each quintuplet, or that you are required to return only one permutation of each quintuplet?

The distinction is important because in some programming languages outputting all permutations will require fewer bytes than outputting just one permutation. (I don't personally have a preference on which way you decide, but it's worth being explicit either way so answerers know what's possible.)

CrSb0001‭ wrote about 1 month ago

copy link

Does "multiple arrays" refer to multiple quintuplets?

Why wouldn't it? I'm basically saying "multiple arrays [of distinct quintuplets".

Does this mean "for each pair of quintuplets, each quintuplet must have at least 2 elements not present in the other", or the stronger "for each quintuplet, at least 2 of its elements must be present in no other quintuplet", or something else?

I mean the latter here.

What should the output be in the following case?
[-1,1,1,1,1,1,3]
Target: 5

The output would be as follows (given from my Python3 answer):

[[1,1,1,1,1], [-1,1,1,1,3]]

If you really want me to, I can add the test case.

CrSb0001‭ wrote about 1 month ago

copy link

Most challenges require fine tuning, so I post mine in the Sandbox category to avoid any answers arriving until the wording is free of potential ambiguity.

...what's wrong with not posting it in the sandbox?

Does this mean that you are permitted to return only one permutation of each quintuplet, or that you are required to return only one permutation of each quintuplet?

It's supposed to mean the former.

Communities

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

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

Problem

1 comment thread