An auditor is looking for groups of four ledger entries that together add up to a suspicious amount. Given the entries nums and the amount target, list every distinct group of four values that sum to target.
Write four_with_total(nums: list[int], target: int) -> list[list[int]].
- A group uses four different positions of
nums, but the values at those positions may be equal. - Report each group as its four values in non-decreasing order, and report each distinct group of values only once, however many ways it can be picked.
- The groups themselves may come in any order. Return
[]if there are none.
four_with_total([2, -1, 0, 1, -2, 0], 0)
# [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]] (any order)
four_with_total([3, 3, 3, 3, 3], 12) # [[3, 3, 3, 3]]
four_with_total([1, 2, 3], 6) # []
four_with_total([5, -5, 10, 0, 0], 10) # [[-5, 0, 5, 10]]
Constraints: 1 <= len(nums) <= 200; values are in [-10^9, 10^9]; target is in [-4 * 10^9, 4 * 10^9].
Checking every choice of four positions is O(n⁴), too slow for 200 values. Aim for O(n³) time and no more than O(1) extra space besides the output.
Show hint
after sorting, fixing the two smallest values of a group leaves you looking for a pair with a known sum in the rest of a sorted list.