18. 4Sum

https://leetcode.com/problems/4sum/

Problem

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Notice that the solution set must not contain duplicate quadruplets.

Example 1:

Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

Example 2:

Input: nums = [], target = 0
Output: []

Constraints:

• 0 <= nums.length <= 200

• -109 <= nums[i] <= 109

• -109 <= target <= 109

Solution

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> quad;
        const int n = nums.size();
        if (n < 4) return quad;
        sort(nums.begin(), nums.end());
        unordered_set<int> seen;
        seen.reserve(n);        
        for (int i = 0; i < n; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) continue;
            for (int j = i + 1; j < n; ++j) {
                if (j > i + 1 && nums[j - 1] == nums[j]) continue;
                for (int k = j + 1; k < n; ++k) {   
                    const int sum = target-nums[i]-nums[j]-nums[k];
                    if (seen.find(sum) != seen.end()) {
                        quad.push_back({nums[i], nums[j], sum, nums[k]});
                        while (k + 1 < n && nums[k] == nums[k + 1]) ++k;
                    }
                    seen.insert(nums[k]);
                }
                seen.clear();
            }
            
        }
        return quad;
    }
};

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        return kSum(nums, 0, 4, target);
    }
    vector<vector<int>> kSum(vector<int>&nums, int start, int k, int target) {
        vector<vector<int>> combs;
        if (k == 2) return twoSum(nums, start, target); 
        for (int i = start; i < nums.size(); ++i) {
            if (i > start && nums[i - 1] == nums[i]) continue;
            auto _combs = kSum(nums, i + 1, k - 1, target - nums[i]);
            for (auto &comb: _combs) {
                comb.push_back(nums[i]);
                combs.push_back(comb);
            }
        }
        return combs;
    }
    vector<vector<int>> twoSum(vector<int>&nums, int start, int target) {
        vector<vector<int>> combs;
        int end = nums.size() - 1;
        while (start < end) {
            const int sum = nums[start] + nums[end];
            if (sum == target) {
                combs.push_back({nums[start++], nums[end--]});
                while (start < end && nums[start - 1] == nums[start]) ++start;
                while (start <= end && nums[end] == nums[end + 1]) --end;
            } else if (sum < target){
                ++start;
            } else {
                --end;
            }
        }
        
        return combs;
    }
};

• #veryimportant

• #twopointer

• #recursive