4Sum

Problem

Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:

• 0 <= a, b, c, d < n
• a, b, c, and d are distinct.
• nums[a] + nums[b] + nums[c] + nums[d] == target

You may return the answer in any order.

Solution Approach

Click - to see solution code

C++

#define ll long long
class Solution {
   public:
    vector<vector<int>> fourSum(vector<int>& arr, int target) {
        int n = arr.size();
        unordered_map<ll, ll> mp;
        set<vector<int>> ans;
        vector<int> a;

        for (int i = 0; i < n; i++) mp[arr[i]]++;
        for (int i = 0; i < n; i++) {
            mp[arr[i]]--;
            for (int j = i + 1; j < n; j++) {
                mp[arr[j]]--;
                for (int k = j + 1; k < n; k++) {
                    mp[arr[k]]--;
                    ll sm = (ll)arr[i] + (ll)arr[k] + (ll)arr[j];
                    if (mp[target - sm]) {
                        a = {arr[i], arr[j], arr[k], int(target - sm)};
                        sort(a.begin(), a.end());
                        ans.insert(a);
                    }
                }
                for (int k = j + 1; k < n; k++) mp[arr[k]]++;
            }
            for (int j = i + 1; j < n; j++) mp[arr[j]]++;
        }
        vector<vector<int>> res;
        for (auto i : ans) res.push_back(i);
        return res;
    }
};