Find All Index Quadruples Summing to a Target Without Losing Positions

Given an integer array nums and an integer target, return every quadruple of indices (i, j, k, l) with i < j < k < l such that nums[i] + nums[j] + nums[k] + nums[l] == target.

Answers are identified by position, not by value: indices refer to the original, unmodified array, and two quadruples that use equal values at different positions are different answers. The interviewer asked for the most efficient approach you can find, so aim to do better than examining every quadruple of indices.

Function Signature

def index_quadruples_with_sum(nums: list[int], target: int) -> list[list[int]]:

Rules

• Each quadruple is returned as a list [i, j, k, l] of four distinct indices in strictly increasing order.
• Every valid quadruple appears exactly once.
• The outer list is sorted in ascending lexicographic order.
• Return an empty list if no quadruple exists, including when len(nums) < 4.

Constraints

• 1 <= len(nums) <= 200
• -10^9 <= nums[i] <= 10^9
• -10^9 <= target <= 10^9
• A sum of four elements can reach 4 * 10^9 in absolute value, which exceeds 2^31 - 1; use 64-bit arithmetic in fixed-width languages. All values stay within 2^53.
• The number of valid quadruples is at most 10^4.

Examples

Example 1

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

The values are 1 + 0 + (-1) + 0, 1 + (-1) + (-2) + 2 and 0 + 0 + (-2) + 2, all equal to 0.

Example 2

Input: nums = [2, 2, 2, 2, 2], target = 8
Output: [[0, 1, 2, 3], [0, 1, 2, 4], [0, 1, 3, 4], [0, 2, 3, 4], [1, 2, 3, 4]]

Every choice of four of the five positions sums to 8. The values are identical, but the index sets differ, so all five are separate answers.

Example 3

Input: nums = [1, 2, 3], target = 6
Output: []

The array has fewer than four elements.