18. 4Sum

📝 Problem Details

• Title: 18. 4Sum
• Link: https://leetcode.com/problems/4sum/
• Difficulty: Medium
• Tags/Categories: Two-Pointers Sorting Arrays

💭What Were My Initial Thoughts?

- similar to 2 and 3sum problems
- brute force could just be a matter of solving for 3sum with an additional nested for loop

🤔What Did I Struggle With?

💡 Explanation of Solution

1. Sort the array
	- first, sort the array to enable efficient traversal and skip duplicate combinatinos

2. Recursive k-Sum function
	- generalise the problem into a kSum function, which reduces the size of the problem recursively until it reaches until it reaches the 2-Sum case

3. Base Case (2-Sum Problem)
	- solve the 2-Sum problem using the two-pointer approach
	- move two pointers (left and right) toward each other while avoiding duplicates

4. Avoiding Duplicates
	- after selecting a number in the kSum function, skip subsequent numberst that are the same to prevent duplicate combinations

⌛ Complexity Analysis

1. **Time Complexity**:
   - Sorting the array: `O(n log n)`.
   - Recursive calls:
     - For `k = 4`, the first loop iterates `O(n)` times.
     - For `k = 3`, the next loop iterates `O(n-1)` times.
     - For `k = 2`, the two-pointer approach runs in `O(n)` time.
   - Overall, the time complexity is approximately `O(n^(k-1))`, where `k` is the sum size. For 4Sum, this is `O(n^3)`.

2. **Space Complexity**:
   - Sorting the array requires `O(n)` extra space.
   - The recursion stack can go up to `O(k)` levels. For 4Sum, this is `O(4)`.
   - Overall, space complexity is `O(n)` due to sorting.

💻 Implementation of Solution

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        // Step 1: Sort the array to enable two-pointer technique and avoid duplicates
        sort(nums.begin(), nums.end());
        // Step 2: Call the generalized kSum function for k=4
        return kSum(nums, target, 4, 0);
    }
 
private:
    vector<vector<int>> kSum(vector<int>& nums, long long target, int k, int start) {
        vector<vector<int>> result;
 
        // Base case: Solve the 2Sum problem using two pointers
        if (k == 2) {
            int left = start, right = nums.size() - 1;
            while (left < right) {
                long long sum = (long long) nums[left] + nums[right];
 
                if (sum == target) {
                    // Add the pair to the result
                    result.push_back({nums[left], nums[right]});
 
                    // Skip duplicates
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    while (left < right && nums[right] == nums[right - 1]) right--;
 
                    // Move pointers inward
                    left++;
                    right--;
                } else if (sum < target) {
                    left++;  // Increase sum
                } else {
                    right--;  // Decrease sum
                }
            }
        } else {
            // Recursive case: Reduce kSum to (k-1)Sum
            for (int i = start; i < nums.size(); i++) {
                // Skip duplicates
                if (i > start && nums[i] == nums[i - 1]) continue;
 
                // Recursive call for (k-1)Sum with updated target and starting index
                auto subResults = kSum(nums, target - nums[i], k - 1, i + 1);
 
                // Append the current number to each result from the recursive call
                for (auto& subResult : subResults) {
                    subResult.push_back(nums[i]);
                    result.push_back(subResult);
                }
            }
        }
 
        return result;
    }
};