Problem Statement

Given an integer array nums of size n and an integer target, find all unique combinations of k elements from nums that add up to the target.

Each combination should be unique, meaning that no duplicate combinations are allowed in the result. The same number can only be used once per combination (you cannot reuse elements), but the array may contain duplicate values.

Return the list of all unique combinations, where each combination is represented as a list of integers. The combinations can be returned in any order.

Examples

Example 1:

Input: nums = [1, 0, -1, 0, -2, 2], target = 0, k = 4
Output: [
         [-2, -1, 1, 2],
         [-2, 0, 0, 2],
         [-1, 0, 0, 1]
        ]
        
Explanation:
There are three unique quadruplets (4-element combinations) that sum up to 0.

Example 2:

Input: nums = [1, 2, 3, 4, 5], target = 10, k = 3
Output: [
         [2, 3, 5],
         [1, 4, 5]
        ]
        
Explanation:
There are two unique triplets (3-elements combinations) that sum up to 10.

Example 3:

Input: nums = [2, 2, 2, 2, 2], target = 8, k = 4
Output: [
         [2, 2, 2, 2]
        ]

Explanation: Only one unique quadruplet (4-element combination) sums up to 8.

Note:

This problem generalizes other sum problems:

• Two sum when k = 2
• Three sum when k = 3
• Four sum when k = 4
• The array may contain duplicates, but each combination in the result should be unique.

Different Approaches

1️⃣ Recursion

Trick: Use a recursive approach to reduce it to a Two Sum problem.

Approach:

1. Sorting the Array: 
   • Start by sorting nums. Sorting allows us to use the two-pointer technique efficiently and makes it easier to skip duplicates.
2. Recursive Reduction:
   • We reduce the K Sum problem to a (K-1) Sum problem by fixing one element at a time and recursively searching for the remaining k-1 elements that add up to the reduced target.
   • For example, for 4 Sum, pick one element and reduce it to a 3 Sum problem with the remaining target. This process continues until we reach the base case.
3. Base Case - Two Sum:
   • The base case is the Two Sum problem, where k = 2. At this point, use the two-pointer technique to find pairs of elements that add up to the target.
   • By starting from opposite ends of the sorted array, we can move pointers inward to efficiently find the pairs.
4. Avoiding Duplicates:
   • To ensure unique combinations, skip over duplicate elements during each iteration at every level of the recursion.

Code:

#include <vector>
#include <algorithm>

class Solution {
public:
    // Helper function for recursive K Sum
    std::vector<std::vector<int>> kSum(std::vector<int>& nums, int target, int k, int start) {
        std::vector<std::vector<int>> result;

        // Base case: Two Sum
        if (k == 2) {
            int left = start, right = nums.size() - 1;
            while (left < right) {
                int sum = nums[left] + nums[right];
                if (sum == target) {
                    result.push_back({nums[left], nums[right]});
                    // Move pointers and skip duplicates
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    left++;
                    right--;
                } else if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        } else { // Recursive case for k > 2
            for (int i = start; i < nums.size(); i++) {
                if (i > start && nums[i] == nums[i - 1]) continue;  // Skip duplicates
                // Fix nums[i] and recursively solve (k-1) sum for the reduced target
                std::vector<std::vector<int>> subsets = kSum(nums, target - nums[i], k - 1, i + 1);
                for (auto& subset : subsets) {
                    subset.insert(subset.begin(), nums[i]);  // Add current number to each subset
                    result.push_back(subset);
                }
            }
        }
        return result;
    }

    // Main function to call kSum with the sorted nums array
    std::vector<std::vector<int>> fourSum(std::vector<int>& nums, int target) {
        std::sort(nums.begin(), nums.end());
        return kSum(nums, target, 4, 0);  // Call kSum for k = 4
    }
};

Complexity Analysis:

• Time Complexity: O(n^(k-1)), where n is the number of elements in nums.
• Space Complexity: O(k) for the recursion stack.

https://www.youtube.com/watch?v=-vu9GpZfqLY