✅☑[C++/C/Java/Python/Javascript ] || 3  Best Approaches || Hash table || 2 pointers || Sorting 🔥
PLEASE UPVOTE IF IT HELPED\n\n---\n\n# Approach\n(also explained in the code)\n\n1. Approach 1: (Using Two Pointers and Sorting with Hash Tables)\n\n2. Approach
# ***PLEASE UPVOTE IF IT HELPED***\n\n---\n\n# Approach\n***(also explained in the code)***\n\n1. **Approach 1:** **(Using Two Pointers and Sorting with Hash Tables)**\n\n2. **Approach 2:** **(Using a Hash Set for Efficiency )**\n\n\n3. **Approach 3:** **(Using Two Pointers and Sorting) (*Simplified*)** ***(Optimized)***\n \n\n# Complexity\n- **Time complexity:**\n1. $$O(n^3)$$\n2. $$O(n^3)$$\n3. $$O(n^3)$$ \n \n- **Space complexity:**\n1. $$O(n)$$\n2. $$O(n)$$\n3. $$O(1)$$\n\n\n# Code\n\n```C++ []\n\n\n                -----------Approach 1------------\n\nclass Solution {\npublic:\n    vector<vector<int>> fourSum(vector<int>& nums, int target) {\n        sort(nums.begin(), nums.end()); // Sort the input array.\n        vector<vector<int>> ans; // Create a vector to store the result.\n        set<vector<int>> pair; // Use a set to store unique quadruplets.\n\n        int n = nums.size();\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\n                while (low < high) {\n                    if (nums[low] + nums[high] < newtarget) {\n                        low++;\n                    } else if (nums[low] + nums[high] > newtarget) {\n                        high--;\n                    } else {\n                        pair.insert({nums[i], nums[j], nums[low], nums[high]});\n                        low++;\n                        high--;\n                    }\n                }\n            }\n        }\n\n        for (auto a : pair) {\n            ans.push_back(a); // Convert the set to a vector for the final result.\n        }\n\n        return ans;\n    }\n};\n\n\n                -----------Approach 2------------\n\nclass Solution {\npublic:\n    vector<vector<int>> fourSum(vector<int>& nums, int target) {\n        set<vector<int>> st; // Use a set to store unique quadruplets.\n        int n = nums.size();\n\n        for (int i = 0; i < n; i++) {\n            for (int j = i + 1; j < n; j++) {\n                set<long long> hash; // Use a set to store unique sums.\n\n                for (int k = j + 1; k < n; k++) {\n                    long long sum = nums[i] + nums[j] + nums[k];\n                    long long forth = target - sum;\n\n                    if (hash.find(forth) != hash.end()) {\n                        vector<int> temp = {nums[i], nums[j], nums[k], (int)forth};\n                        sort(temp.begin(), temp.end());\n                        st.insert(temp);\n                    }\n                    hash.insert(nums[k]);\n                }\n            }\n        }\n\n        vector<vector<int>> ans(st.begin(), st.end()); // Convert the set to a vector for the final result.\n        return ans;\n    }\n};\n\n\n                -----------Approach 3------------\n\nclass Solution {\npublic:\n    vector<vector<int>> fourSum(vector<int>& nums, int target) {\n        sort(nums.begin(), nums.end()); // Sort the input array.\n        vector<vector<int>> ans; // Create a vector to store the result.\n\n        int n = nums.size();\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\n                while (low < high) {\n                    if (nums[low] + nums[high] < newtarget) {\n                        low++;\n                    } else if (nums[low] + nums[high] > newtarget) {\n                        high--;\n                    } else {\n                        ans.push_back({nums[i], nums[j], nums[low], nums[high]});\n                        int index1 = low, index2 = high;\n                        while (low < high && nums[low] == nums[index1]) low++;\n                        while (low < high && nums[high] == nums[index2]) 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\n        return ans;\n    }\n};\n\n\n\n\n\n```\n```Java []\n\n                -----------Approach 1------------\n\nclass Solution {\n    public List<List<Integer>> fourSum(int[] nums, int target) {\n        Arrays.sort(nums); // Sort the input array.\n        List<List<Integer>> ans = new ArrayList<>(); // Create a list to store the result.\n        Set<List<Integer>> pair = new HashSet<>(); // Use a set to store unique quadruplets.\n\n        int n = nums.length;\n        for (int i = 0; i < n - 3; i++) {\n            for (int j = i + 1; j < n - 2; j++) {\n                long newTarget = (long) target - ((long) nums[i] + (long) nums[j]);\n                int low = j + 1, high = n - 1;\n\n                while (low < high) {\n                    if (nums[low] + nums[high] < newTarget) {\n                        low++;\n                    } else if (nums[low] + nums[high] > newTarget) {\n                        high--;\n                    } else {\n                        pair.add(Arrays.asList(nums[i], nums[j], nums[low], nums[high]));\n                        low++;\n                        high--;\n                    }\n                }\n            }\n        }\n\n        ans.addAll(pair);\n        return ans;\n    }\n}\n\n\n                -----------Approach 2------------\n\nclass Solution {\n    public List<List<Integer>> fourSum(int[] nums, int target) {\n        Set<List<Integer>> set = new HashSet<>(); // Use a set to store unique quadruplets.\n        int n = nums.length;\n\n        for (int i = 0; i < n; i++) {\n            for (int j = i + 1; j < n; j++) {\n                Set<Long> hash = new HashSet<>(); // Use a set to store unique sums.\n\n                for (int k = j + 1; k < n; k++) {\n                    long sum = (long) nums[i] + nums[j] + nums[k];\n                    long forth = (long) target - sum;\n\n                    if (hash.contains(forth)) {\n                        List<Integer> temp = Arrays.asList(nums[i], nums[j], nums[k], (int) forth);\n                        Collections.sort(temp);\n                        set.add(temp);\n                    }\n                    hash.add((long) nums[k]);\n                }\n            }\n        }\n\n        return new ArrayList<>(set);\n    }\n}\n\n\n                -----------Approach 3------------\n\nclass Solution {\n    public List<List<Integer>> fourSum(int[] nums, int target) {\n        Arrays.sort(nums); // Sort the input array.\n        List<List<Integer>> ans = new ArrayList<>(); // Create a list to store the result.\n\n        int n = nums.length;\n        for (int i = 0; i < n - 3; i++) {\n            for (int j = i + 1; j < n - 2; j++) {\n                long newTarget = (long) target - ((long) nums[i] + (long) nums[j]);\n                int low = j + 1, high = n - 1;\n\n                while (low < high) {\n                    if (nums[low] + nums[high] < newTarget) {\n                        low++;\n                    } else if (nums[low] + nums[high] > newTarget) {\n                        high--;\n                    } else {\n                        ans.add(Arrays.asList(nums[i], nums[j], nums[low], nums[high]));\n                        int index1 = low, index2 = high;\n                        while (low < high && nums[low] == nums[index1]) low++;\n                        while (low < high && nums[high] == nums[index2]) 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\n        return ans;\n    }\n}\n\n\n\n```\n\n```C []\n\n\n                -----------Approach 1------------\n\n#include <stdio.h>\n#include <stdlib.h>\n#include <string.h>\n\nint compare(const void* a, const void* b) {\n    return (*(int*)a - *(int*)b);\n}\n\nint** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {\n    qsort(nums, numsSize, sizeof(int), compare);\n    int** ans = NULL;\n    *returnSize = 0;\n\n    for (int i = 0; i < numsSize - 3; i++) {\n        if (i > 0 && nums[i] == nums[i - 1]) continue;\n        for (int j = i + 1; j < numsSize - 2; j++) {\n            if (j > i + 1 && nums[j] == nums[j - 1]) continue;\n            long long newTarget = (long long)target - nums[i] - nums[j];\n            int low = j + 1, high = numsSize - 1;\n\n            while (low < high) {\n                long long sum = nums[low] + nums[high];\n                if (sum < newTarget) {\n                    low++;\n                } else if (sum > newTarget) {\n                    high--;\n                } else {\n                    (*returnSize)++;\n                    ans = (int**)realloc(ans, (*returnSize) * sizeof(int*));\n                    ans[*returnSize - 1] = (int*)malloc(4 * sizeof(int));\n                    ans[*returnSize - 1][0] = nums[i];\n                    ans[*returnSize - 1][1] = nums[j];\n                    ans[*returnSize - 1][2] = nums[low];\n                    ans[*returnSize - 1][3] = nums[high];\n                    while (low < high && nums[low] == nums[low + 1]) low++;\n                    while (low < high && nums[high] == nums[high - 1]) high--;\n                    low++;\n                    high--;\n                }\n            }\n        }\n    }\n\n    *returnColumnSizes = (int*)malloc(*returnSize * sizeof(int));\n    for (int i = 0; i < *returnSize; i++) {\n        (*returnColumnSizes)[i] = 4;\n    }\n\n    return ans;\n}\n\n\n                -----------Approach 2------------\n\n#include <stdio.h>\n#include <stdlib.h>\n#include <string.h>\n\nint compare(const void* a, const void* b) {\n    return (*(int*)a - *(int*)b);\n}\n\nint** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {\n    int** ans = NULL;\n    *returnSize = 0;\n\n    qsort(nums, numsSize, sizeof(int), compare);\n\n    for (int i = 0; i < numsSize; i++) {\n        if (i > 0 && nums[i] == nums[i - 1]) continue;\n        for (int j = i + 1; j < numsSize; j++) {\n            if (j > i + 1 && nums[j] == nums[j - 1]) continue;\n            long long newTarget = (long long)target - nums[i] - nums[j];\n            int low = j + 1, high = numsSize - 1;\n\n            while (low < high) {\n                long long sum = (long long)nums[low] + nums[high];\n                if (sum < newTarget) {\n                    low++;\n                } else if (sum > newTarget) {\n                    high--;\n                } else {\n                    (*returnSize)++;\n                    ans = (int**)realloc(ans, (*returnSize) * sizeof(int*));\n                    ans[*returnSize - 1] = (int*)malloc(4 * sizeof(int));\n                    ans[*returnSize - 1][0] = nums[i];\n                    ans[*returnSize - 1][1] = nums[j];\n                    ans[*returnSize - 1][2] = nums[low];\n                    ans[*returnSize - 1][3] = nums[high];\n                    while (low < high && nums[low] == nums[low + 1]) low++;\n                    while (low < high && nums[high] == nums[high - 1]) high--;\n                    low++;\n                    high--;\n                }\n            }\n        }\n    }\n\n    *returnColumnSizes = (int*)malloc(*returnSize * sizeof(int));\n    for (int i = 0; i < *returnSize; i++) {\n        (*returnColumnSizes)[i] = 4;\n    }\n\n    return ans;\n}\n\n\n                -----------Approach 3------------\n\n\n#include <stdio.h>\n#include <stdlib.h>\n#include <string.h>\n\nint compare(const void* a, const void* b) {\n    return (*(int*)a - *(int*)b);\n}\n\nint** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes) {\n    int** ans = NULL;\n    *returnSize = 0;\n\n    qsort(nums, numsSize, sizeof(int), compare);\n\n    for (int i = 0; i < numsSize - 3; i++) {\n        if (i > 0 && nums[i] == nums[i - 1]) continue;\n        for (int j = i + 1; j < numsSize - 2; j++) {\n            if (j > i + 1 && nums[j] == nums[j - 1]) continue;\n            long long newTarget = (long long)target - nums[i] - nums[j];\n            int low = j + 1, high = numsSize - 1;\n\n            while (low < high) {\n                long long sum = (long long)nums[low] + nums[high];\n                if (sum < newTarget) {\n                    low++;\n                } else if (sum > newTarget) {\n                    high--;\n                } else {\n                    (*returnSize)++;\n                    ans = (int**)realloc(ans, (*returnSize) * sizeof(int*));\n                    ans[*returnSize - 1] = (int*)malloc(4 * sizeof(int));\n                    ans[*returnSize - 1][0] = nums[i];\n                    ans[*returnSize - 1][1] = nums[j];\n                    ans[*returnSize - 1][2] = nums[low];\n                    ans[*returnSize - 1][3] = nums[high];\n                    while (low < high && nums[low] == nums[low + 1]) low++;\n                    while (low < high && nums[high] == nums[high - 1]) high--;\n                    low++;\n                    high--;\n                }\n            }\n        }\n    }\n\n    *returnColumnSizes = (int*)malloc(*returnSize * sizeof(int));\n    for (int i = 0; i < *returnSize; i++) {\n        (*returnColumnSizes)[i] = 4;\n    }\n\n    return ans;\n}\n\n\n\n\n```\n\n```python []\n\n\n                -----------Approach 1------------\n\ndef fourSum(nums, target):\n    nums.sort()\n    ans = set()\n    n = len(nums)\n    \n    for i in range(n - 3):\n        for j in range(i + 1, n - 2):\n            new_target = target - nums[i] - nums[j]\n            low, high = j + 1, n - 1\n\n            while low < high:\n                if nums[low] + nums[high] < new_target:\n                    low += 1\n                elif nums[low] + nums[high] > new_target:\n                    high -= 1\n                else:\n                    ans.add((nums[i], nums[j], nums[low], nums[high]))\n                    low += 1\n                    high -= 1\n    \n    return list(ans)\n\n\n                -----------Approach 2------------\n\ndef fourSum(nums, target):\n    ans = set()\n    n = len(nums)\n\n    for i in range(n):\n        for j in range(i + 1, n):\n            hash_set = set()\n\n            for k in range(j + 1, n):\n                current_sum = nums[i] + nums[j] + nums[k]\n                fourth = target - current_sum\n\n                if fourth in hash_set:\n                    ans.add(tuple(sorted([nums[i], nums[j], nums[k], fourth])))\n                hash_set.add(nums[k])\n    \n    return list(ans)\n\n\n                -----------Approach 3------------\n\n\ndef fourSum(nums, target):\n    nums.sort()\n    ans = []\n    n = len(nums)\n    \n    for i in range(n - 3):\n        if i > 0 and nums[i] == nums[i - 1]:\n            continue\n        for j in range(i + 1, n - 2):\n            if j > i + 1 and nums[j] == nums[j - 1]:\n                continue\n            new_target = target - nums[i] - nums[j]\n            low, high = j + 1, n - 1\n\n            while low < high:\n                current_sum = nums[low] + nums[high]\n                if current_sum < new_target:\n                    low += 1\n                elif current_sum > new_target:\n                    high -= 1\n                else:\n                    ans.append([nums[i], nums[j], nums[low], nums[high]])\n                    while low < high and nums[low] == nums[low + 1]:\n                        low += 1\n                    while low < high and nums[high] == nums[high - 1]:\n                        high -= 1\n                    low += 1\n                    high -= 1\n    return ans\n\n\n\n\n```\n\n```javascript []\n\n\n                -----------Approach 1------------\n\nvar fourSum = function(nums, target) {\n    nums.sort((a, b) => a - b);\n    const ans = new Set();\n    const n = nums.length;\n\n    for (let i = 0; i < n - 3; i++) {\n        for (let j = i + 1; j < n - 2; j++) {\n            const newTarget = target - nums[i] - nums[j];\n            let low = j + 1, high = n - 1;\n\n            while (low < high) {\n                if (nums[low] + nums[high] < newTarget) {\n                    low++;\n                } else if (nums[low] + nums[high] > newTarget) {\n                    high--;\n                } else {\n                    ans.add([nums[i], nums[j], nums[low], nums[high]].toString());\n                    low++;\n                    high--;\n                }\n            }\n        }\n    }\n\n    return Array.from(ans).map(item => item.split(\',\').map(Number));\n};\n\n\n                -----------Approach 2------------\n\nvar fourSum = function(nums, target) {\n    const ans = new Set();\n    const n = nums.length;\n\n    for (let i = 0; i < n; i++) {\n        for (let j = i + 1; j < n; j++) {\n            const hash = new Set();\n\n            for (let k = j + 1; k < n; k++) {\n                const currentSum = nums[i] + nums[j] + nums[k];\n                const fourth = target - currentSum;\n\n                if (hash.has(fourth)) {\n                    ans.add([nums[i], nums[j], nums[k], fourth].sort((a, b) => a - b).toString());\n                }\n                hash.add(nums[k]);\n            }\n        }\n    }\n\n    return Array.from(ans).map(item => item.split(\',\').map(Number));\n};\n\n\n                -----------Approach 3------------\n\n\nvar fourSum = function(nums, target) {\n    nums.sort((a, b) => a - b);\n    const ans = [];\n    const n = nums.length;\n\n    for (let i = 0; i < n - 3; i++) {\n        if (i > 0 && nums[i] === nums[i - 1]) continue;\n        for (let j = i + 1; j < n - 2; j++) {\n            if (j > i + 1 && nums[j] === nums[j - 1]) continue;\n            const newTarget = target - nums[i] - nums[j];\n            let low = j + 1, high = n - 1;\n\n            while (low < high) {\n                const currentSum = nums[low] + nums[high];\n                if (currentSum < newTarget) {\n                    low++;\n                } else if (currentSum > newTarget) {\n                    high--;\n                } else {\n                    ans.push([nums[i], nums[j], nums[low], nums[high]]);\n                    while (low < high && nums[low] === nums[low + 1]) low++;\n                    while (low < high && nums[high] === nums[high - 1]) high--;\n                    low++;\n                    high--;\n                }\n            }\n        }\n    }\n\n    return ans;\n};\n\n\n\n\n```\n\n\n\n\n\n# ***PLEASE UPVOTE IF IT HELPED***\n\n---\n\n\n---\n\n\n
['Array', 'Hash Table', 'Two Pointers', 'Binary Search', 'C', 'Sorting', 'Python', 'C++', 'Java', 'JavaScript']