Four Numbers to a Target

Medium

You are given an integer array values and an integer total. Find every distinct set of four elements (at different indices) whose sum equals total. Sets are compared by value: two sets made of the same numbers are the same set, even if the numbers come from different positions. Return each set as a list of four numbers. Neither the order of the sets nor the order of numbers inside a set matters.

Example 1

values=[3, -1, 2, 0, -2, 1], total=2 → [[-2, -1, 2, 3], [-2, 0, 1, 3], [-1, 0, 1, 2]]

Three distinct sets add up to 2: -2, -1, 2, 3; -2, 0, 1, 3; and -1, 0, 1, 2.

Example 2

values=[5, 5, 5, 5, 5, 5], total=20 → [[5, 5, 5, 5]]

There are many index quadruples, but only one set of values: 5, 5, 5, 5.

Example 3

values=[1, 2, 3], total=6 → []

There are fewer than four numbers, so the answer is empty.

Constraints

1 ≤ len(values) ≤ 200
-10⁹ ≤ values[i] ≤ 10⁹
-10⁹ ≤ total ≤ 10⁹

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Two Pointers Sorting

Similar problems

Zero-Sum Triples Medium Triple Sum Nearest the Target Medium Flags in Three Colors Medium Studios for Recording Sessions Medium Triples Under a Limit Medium

Input

values=[3, -1, 2, 0, -2, 1], total=2

Expected

[[-2, -1, 2, 3], [-2, 0, 1, 3], [-1, 0, 1, 2]]

Run checks the first 3 tests in your browser. Submit checks all 87 tests on the server, hidden ones included.