BruteForce to Better to Optimal | C++ Multiple Solutions
cpp\ntypedef long long ll;\n\n\n// Bruteforce | O(n^4) time | O(n) space\nclass Solution {\npublic:\n    vector<vector<int>> fourSum(vector<int> &nums, int targ
```cpp\ntypedef long long ll;\n\n\n// Bruteforce | O(n^4) time | O(n) space\nclass Solution {\npublic:\n    vector<vector<int>> fourSum(vector<int> &nums, int target) {\n        int n = nums.size();\n        set<vector<int>> st;\n        sort(nums.begin(), nums.end());\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 t = k + 1; t < n; t++) {\n                        if ((ll)nums[i] + nums[j] + nums[k] + nums[t] == (ll)target) {\n                            vector<int> quad = {nums[i], nums[j], nums[k], nums[t]};\n                            st.insert(quad);\n                        }\n                    }\n                }\n            }\n        }\n        vector<vector<int>> res(st.begin(), st.end());\n        return res;\n    }\n};\n\n\n// Bruteforce | O(n^4) time | O(1) space\nclass Solution {\npublic:\n    vector<vector<int>> fourSum(vector<int> &nums, int target) {\n        int n = nums.size();\n        vector<vector<int>> res;\n        sort(nums.begin(), nums.end());\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 t = k + 1; t < n; t++) {\n                        if ((ll)nums[i] + nums[j] + nums[k] + nums[t] == (ll)target) {\n                            vector<int> quad = {nums[i], nums[j], nums[k], nums[t]};\n                            res.push_back(quad);\n                        }\n                        while (t < n - 1 && nums[t] == nums[t + 1]) t++;\n                    }\n                    while (k < n - 1 && nums[k] == nums[k + 1]) k++;\n                }\n                while (j < n - 1 && nums[j] == nums[j + 1]) j++;\n            }\n            while (i < n - 1 && nums[i] == nums[i + 1]) i++;\n        }\n        return res;\n    }\n};\n\n\n\n// Optimal | O(n^3 * log(n)) time | O(1) space\nclass Solution {\npublic:\n    vector<vector<int>> fourSum(vector<int> &nums, int target) {\n        int n = nums.size();\n        vector<vector<int>> res;\n        sort(nums.begin(), nums.end());\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                    ll sumOfThree = (ll)nums[i] + (ll)nums[j] + (ll)nums[k];\n                    int fourthNum = target - sumOfThree;\n                    if (binary_search(nums.begin() + k + 1, nums.end(), fourthNum)) {\n                        vector<int> quad = {nums[i], nums[j], nums[k], fourthNum};\n                        res.push_back(quad);\n                    }\n                    while (k < n - 1 && nums[k] == nums[k + 1]) k++;\n                }\n                while (j < n - 1 && nums[j] == nums[j + 1]) j++;\n            }\n            while (i < n - 1 && nums[i] == nums[i + 1]) i++;\n        }\n        return res;\n    }\n};\n\n\n\n// Most Optimal | O(n^3) time | O(1) space\nclass Solution {\npublic:\n    vector<vector<int>> fourSum(vector<int> &nums, int target) {\n        int n = nums.size();\n        vector<vector<int>> res;\n        sort(nums.begin(), nums.end());\n        for (int i = 0; i < n - 3; i++) {\n            for (int j = i + 1; j < n - 2; j++) {\n                int l = j + 1, r = n - 1;\n                ll remSum = (ll)target - (ll)nums[i] - (ll)nums[j];\n                while (l < r) {\n                    ll sumOfLastTwo = nums[l] + nums[r];\n                    if (sumOfLastTwo < remSum) l++;\n                    else if (sumOfLastTwo > remSum) r--;\n                    else {\n                        vector<int> quad = {nums[i], nums[j], nums[l], nums[r]};\n                        res.push_back(quad);\n                        while (l < r && nums[l] == quad[2]) l++;\n                        while (l < r && nums[r] == quad[3]) r--;\n                    }\n                }\n                while (j < n - 1 && nums[j] == nums[j + 1]) j++;\n            }\n            while (i < n - 1 && nums[i] == nums[i + 1]) i++;\n        }\n        return res;\n    }\n};\n```
['C', 'C++']