Generalized N-Sum
Bloomberg LP● HardNEW GRADONSITE INTERVIEWProblem statement
Given an integer array nums, an integer n, and an integer target, return every unique combination of exactly n values whose sum is target.
- Each array index may be selected at most once.
- Values within each combination must be in nondecreasing order.
- Return unique combinations in lexicographic order.
Function
nSum(nums: int[], n: int, target: int) → int[][]Examples
Example 1
nums = [1,0,-1,0,-2,2]n = 4target = 0return = [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]These are the three unique four-value combinations summing to zero.
Example 2
nums = [2,2,2,2,2]n = 4target = 8return = [[2,2,2,2]]Many index choices yield the same value combination, which appears only once.
Example 3
nums = [1,2,3]n = 2target = 10return = []No pair reaches the target.
Constraints
2 <= nums.length <= 50.2 <= n <= min(5, nums.length).-10^6 <= nums[i], target <= 10^6.- Intermediate sums fit in signed 64-bit integers.