All problems

4Sum

Medium · two pointers

You are given a list of integers nums and an integer target. Find every group of four numbers, taken from four different positions in nums, whose sum is exactly target.

Write each group in ascending order, for example [1, 2, 5, 9]. Never list the same group twice, even when its values can be picked from several positions. The groups themselves may be returned in any order. If no group adds up to target, return an empty list.

Examples

Example 1

Input: nums = [4, 1, 3, 2, 0, 5], target = 10

Output: [[0, 1, 4, 5], [0, 2, 3, 5], [1, 2, 3, 4]]

Each of these three groups adds up to 10. The groups use different positions, and no other four numbers reach 10.

Example 2

Input: nums = [2, 2, 2, 2, 2, 2], target = 8

Output: [[2, 2, 2, 2]]

Fifteen different choices of positions give the same four values, so the group is listed once.

Example 3

Input: nums = [1, 2, 3, 4], target = 20

Output: []

The only group is 1 + 2 + 3 + 4 = 10, which is not 20.

Constraints