JAVA | 2 approaches | Brute and Optimal
Please Upvote :D\n##### 1. Brute force approach (TLE - 288/291 passed):\n\nclass Solution {\n    public List<List<Integer>> fourSum(int[] nums, int target) {\n 
### **Please Upvote** :D\n##### 1. Brute force approach (TLE - 288/291 passed):\n```\nclass Solution {\n    public List<List<Integer>> fourSum(int[] nums, int target) {\n        int n = nums.length;\n        if (n < 4) return new ArrayList<>(); // it\'d still be handled even if we don\'t write this condition\n        Arrays.sort(nums);\n\n        Set<List<Integer>> ans = new HashSet<>();\n\n        for (int i = 0; i < n; i++) \n            for (int j =  i + 1; j < n; j++) \n                for (int k =  j + 1; k < n; k++) \n                    for (int l = k + 1; l < n; l++) \n                        if (nums[i] + nums[j] + nums[k] + nums[l] == target) \n                            ans.add(Arrays.asList(nums[i], nums[j], nums[k], nums[l]));\n\n        return new ArrayList(ans);\n    }\n}\n\n// TC: O(n * logn) + O(n ^ 4) => O(n ^ 4)\n// SC: O(1) - Ignoring output array\n```\n##### 2. Optimal solution (Two pointers):\nWe iterate using the first for loop and find the remaining 3 elements by the same **[3Sum](https://leetcode.com/problems/3sum/discuss/2397624/JAVA-or-3-approaches)** approach.\n\nOr we can say, we find the first two elements using nested for loops and find the remaining 2 elements by the **[TwoSum](https://leetcode.com/problems/two-sum/discuss/2345909/Java-solution-(brute-force-and-optimized))** approach.\n```\nclass Solution {\n    public List<List<Integer>> fourSum(int[] nums, int target) {\n        List<List<Integer>> ans = new ArrayList<>();\n        int n = nums.length;\n\n        Arrays.sort(nums);\n\n        for (int i = 0; i < n; i++) {\n            for (int j = i + 1; j < n; j++) {\n\n                long target2 = (long) target - (long) nums[i] - (long) nums[j];\n                int lo = j + 1, hi = n - 1;\n\n                while (lo < hi) {\n                    int twoSum = nums[lo] + nums[hi];\n\n                    if (twoSum < target2) lo++;\n                    else if (twoSum > target2) hi--;\n                    else {\n                        List<Integer> quad = Arrays.asList(nums[i], nums[j], nums[lo], nums[hi]);\n                        ans.add(quad);\n\n                        while (lo < hi && nums[lo] == quad.get(2)) lo++;\n                        while (lo < hi && nums[hi] == quad.get(3)) hi--;\n                    }\n                }\n\n                while (j + 1 < n && nums[j] == nums[j + 1]) j++;\n            }\n\n            while (i + 1 < n && nums[i] == nums[i + 1]) i++;\n        }\n\n        return ans;\n    }\n}\n\n// TC: O(n * logn) + O(n ^ 3) => O(n ^ 3)\n// SC: O(1) - ignoring the output array\n```
['Two Pointers', 'Java']