✅☑️ Best C++ 3 Solution || Two Pointers || Sorting || Hash Table || Brute Force->Optimize.
Intuition\n Describe your first thoughts on how to solve this problem. \nWe can solve this question using Multiple Approaches. (Here I have explained all the po
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nWe can solve this question using Multiple Approaches. (Here I have explained all the possible solutions of this problem).\n\n1. Solved using Array(Four Nested Loop) + Sorting + Hash Table(set). Brute Force Approach.\n2. Solved using Array(Three Nested Loop) + Sorting + Hash Table(set).\n3. Solved using Array(Three Nested Loop) + Sorting. Optimized Approach.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nWe can easily understand the All the approaches by seeing the code which is easy to understand with comments.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nTime complexity is given in code comment.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nSpace complexity is given in code comment.\n\n# Code\n```\n/*\n\n    Time Complexity : O(N^4), Here Four nested loop creates the time complexity. Where N is the size of the\n    array(nums).\n\n    Space Complexity : O(N), Hash Table(set) space.\n\n    Solved using Array(Four Nested Loop) + Sorting + Hash Table(set). Brute Force Approach.\n\n    Note : this will give TLE.\n\n*/\n\n\n/***************************************** Approach 1 *****************************************/\n\nclass Solution {\npublic:\n    vector<vector<int>> fourSum(vector<int>& nums, int target) {\n        int n = nums.size();\n        sort(nums.begin(), nums.end());\n        set<vector<int>> set;\n        vector<vector<int>> output;\n        for(int i=0; i<n-3; i++){\n            for(int j=i+1; j<n-2; j++){\n                for(int k=j+1; k<n-1; k++){\n                    for(int l=k+1; l<n; l++){\n                        if((long long)nums[i] + (long long)nums[j] + (long long)nums[k] + \n                        (long long)nums[l] == target){\n                            set.insert({nums[i], nums[j], nums[k], nums[l]});\n                        }\n                    }\n                }\n            }\n        }\n        for(auto it : set){\n            output.push_back(it);\n        }\n        return output;\n    }\n};\n\n\n\n\n\n\n/*\n\n    Time Complexity : O(N^3), Here Three nested loop creates the time complexity. Where N is the size of the\n    array(nums).\n\n    Space Complexity : O(N), Hash Table(set) space.\n\n    Solved using Array(Three Nested Loop) + Sorting + Hash Table(set).\n\n*/\n\n\n/***************************************** Approach 2 *****************************************/\n\nclass Solution {\npublic:\n    vector<vector<int>> fourSum(vector<int>& nums, int target) {\n        int n = nums.size();\n        sort(nums.begin(), nums.end());\n        set<vector<int>> set;\n        vector<vector<int>> output;\n        for(int i=0; i<n-3; i++){\n            for(int j=i+1; j<n-2; j++){\n                long long newTarget = (long long)target - (long long)nums[i] - (long long)nums[j];\n                int low = j+1, high = n-1;\n                while(low < high){\n                    if(nums[low] + nums[high] < newTarget){\n                        low++;\n                    }\n                    else if(nums[low] + nums[high] > newTarget){\n                        high--;\n                    }\n                    else{\n                        set.insert({nums[i], nums[j], nums[low], nums[high]});\n                        low++; high--;\n                    }\n                }\n            }\n        }\n        for(auto it : set){\n            output.push_back(it);\n        }\n        return output;\n    }\n};\n\n\n\n\n\n\n/*\n\n    Time Complexity : O(N^3), Here Three nested loop creates the time complexity. Where N is the size of the\n    array(nums).\n\n    Space Complexity : O(1), Constant space. Extra space is only allocated for the Vector(output), however the\n    output does not count towards the space complexity.\n\n    Solved using Array(Three Nested Loop) + Sorting. Optimized Approach.\n\n*/\n\n\n/***************************************** Approach 3 *****************************************/\n\nclass Solution {\npublic:\n    vector<vector<int>> fourSum(vector<int>& nums, int target) {\n        int n = nums.size();\n        sort(nums.begin(), nums.end());\n        vector<vector<int>> output;\n        for(int i=0; i<n-3; i++){\n            for(int j=i+1; j<n-2; j++){\n                long long newTarget = (long long)target - (long long)nums[i] - (long long)nums[j];\n                int low = j+1, high = n-1;\n                while(low < high){\n                    if(nums[low] + nums[high] < newTarget){\n                        low++;\n                    }\n                    else if(nums[low] + nums[high] > newTarget){\n                        high--;\n                    }\n                    else{\n                        output.push_back({nums[i], nums[j], nums[low], nums[high]});\n                        int tempIndex1 = low, tempIndex2 = high;\n                        while(low < high && nums[low] == nums[tempIndex1]) low++;\n                        while(low < high && nums[high] == nums[tempIndex2]) high--;\n                    }\n                }\n                while(j+1 < n && nums[j] == nums[j+1]) j++;\n            }\n            while(i+1 < n && nums[i] == nums[i+1]) i++;\n        }\n        return output;\n    }\n};\n\n```\n\n***IF YOU LIKE THE SOLUTION THEN PLEASE UPVOTE MY SOLUTION BECAUSE IT GIVES ME MOTIVATION TO REGULARLY POST THE SOLUTION.***\n\n![WhatsApp Image 2023-02-10 at 19.01.02.jpeg](https://assets.leetcode.com/users/images/0a95fea4-64f4-4502-82aa-41db6d77c05c_1676054939.8270252.jpeg)
['Array', 'Hash Table', 'Two Pointers', 'Sorting', 'C++']