## Return Every Index Pair Whose Values Sum to a Target ### Problem Implement `all_pairs_sum(nums, target)`. Given an unordered array of integers, return every pair of distinct zero-based indices whose values sum to `target`. ### Output Contract - Represent a pair as `[i, j]` with `i < j`. - Return each index pair exactly once. - Treat equal values at different indices as distinct elements. - Sort the result lexicographically by `i` and then `j`. ### Examples ```text nums = [1, 3, 2, 2, 3] target = 4 result = [[0, 1], [0, 4], [2, 3]] ``` ```text nums = [0, 0, 0] target = 0 result = [[0, 1], [0, 2], [1, 2]] ``` ### Requirements - Use a hash-based approach rather than checking every pair directly. - Preserve every prior index for a value; a single stored index is insufficient when duplicates occur. - Account for the fact that the output itself may contain a quadratic number of pairs. - State the expected time and space complexity in terms of `n`, the input length, and `P`, the number of returned pairs. ```hint Use duplicates as a test case Before choosing what each hash-map entry stores, trace `[2, 2, 2]` and list every distinct index pair that must survive. ``` ### Discussion Prompts 1. What are the keys and values in the hash map? 2. Why must each value be a list of indices rather than one index? 3. Why is the current index inserted only after its complement has been processed? 4. When does the running time exceed linear even though hash lookup is expected constant time? 5. What are the trade-offs relative to the direct quadratic scan?