Problem Statement

For an input array and target value, return all distinct n-element tuples where the sum equals the target. The solution must avoid duplicate combinations in the result.

Example: 
Input: [1, 0, -1, 0, -2, 2], target = 0, n = 4
Output: [[-2, -1, 1, 2], [-2, 0, 0, 2], [-1, 0, 0, 1]]

Generalized Solution

The approach uses recursion with a base case for 2-sum and reduces larger problems to smaller subproblems. The array is first sorted to enable efficient two-pointer searching and duplicate avoidance.

public static List<List<Integer>> findNSumCombinations(int[] numbers, int targetSum, int n) {
    Arrays.sort(numbers);
    return computeCombinations(numbers, 0, n, targetSum);
}

private static List<List<Integer>> computeCombinations(int[] numbers, int startIndex, int count, int target) {
    List<List<Integer>> combinations = new ArrayList<>();
    
    if (count == 2) {
        int left = startIndex;
        int right = numbers.length - 1;
        Set<List<Integer>> seenPairs = new HashSet<>();
        
        while (left < right) {
            int currentSum = numbers[left] + numbers[right];
            if (currentSum == target) {
                List<Integer> pair = Arrays.asList(numbers[left], numbers[right]);
                if (!seenPairs.contains(pair)) {
                    combinations.add(pair);
                    seenPairs.add(pair);
                }
                left++;
                right--;
            } else if (currentSum < target) {
                left++;
            } else {
                right--;
            }
        }
        return combinations;
    } else {
        for (int i = startIndex; i < numbers.length - count + 1; i++) {
            List<List<Integer>> subCombinations = 
                computeCombinations(numbers, i + 1, count - 1, target - numbers[i]);
            
            for (List<Integer> subList : subCombinations) {
                subList.add(numbers[i]);
                combinations.add(subList);
            }
        }
    }
    return combinations;
}

Key Implementation Details

• Array sorting enables efficient two-pointer technique for the base case
• HashSet prevents duplicate pairs in the 2-sum base case
• Recursive reduction: n-sum becomes (n-1)-sum with adjusted target
• Results are built by combining current element with subproblem solutions