Four Sum

Return all the different groups of four values from nums that add up to target. Each group is written in increasing order, there must be no repeated group, and the list of groups is sorted. Values may be reused only when they appear several times in nums.

The starter code tries every group of four positions. It is correct but too slow. Make it fast.

Examples

Example 1

Input:

four_sum([1, 0, -1, 0, -2, 2], 0)

Output:

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

The groups are [-2, -1, 1, 2], [-2, 0, 0, 2] and [-1, 0, 0, 1].

Example 2

Input:

four_sum([2, 2, 2, 2, 2], 8)

Output:

[[2, 2, 2, 2]]

Only one different group: [2, 2, 2, 2].

Constraints

• 0 <= len(nums) <= 150
• -10**4 <= nums[i] <= 10**4
• -4 * 10**4 <= target <= 4 * 10**4