GENERAL BACKTRACKING SOLUTION FOR N-SUM SERIES QUESTIONS. CHECK IT OUT!! [CPP/JAVA/PYTHON]
Intuition\n It first checks if there are fewer than 4 elements in the input array. If so, it returns an empty vector since there can\'t be any valid quadruplets
# Intuition\n* It first checks if there are fewer than 4 elements in the input array. If so, it returns an empty vector since there can\'t be any valid quadruplets.\n\n* It sorts the input array in ascending order to simplify the process of finding unique quadruplets.\n\n* It initializes a temporary vector temp to store combinations and a result vector res to store valid quadruplets.\n\n* It calls the helper function with the sorted array, target value, and other parameters to find quadruplets.\n\n* The helper function uses recursion to find unique combinations of numbers. It has two modes of operation: when it needs more than 2 numbers to complete the combination (in this case, it searches for the first number in the combination), and when it needs exactly 2 numbers (in this case, it performs a two-pointer approach).\n\n* In the two-pointer approach, it uses two pointers, l and r, that start from the beginning and end of the sorted array. It calculates the sum of two elements and adjusts the pointers accordingly to find all pairs of numbers that sum up to the target.(  Same as 1.TWO_SUM )\n\n* It avoids duplicates in both modes of operation to ensure that the result contains only unique quadruplets.\n\n* Valid quadruplets found during the process are stored in the res vector.\n\n* Finally, it returns the res vector containing all unique quadruplets.\n\n# CPP\n```\nclass Solution {\npublic:\n    vector<vector<int>> fourSum(vector<int>& nums, int target) {\n        if (nums.size() < 4) {\n            return {}; // If there are fewer than 4 elements, return an empty vector.\n        }\n        sort(nums.begin(), nums.end()); // Sort the input array in ascending order.\n        vector<int> temp; // Temporary vector to store combinations.\n        vector<vector<int>> res; // Result vector to store valid quadruplets.\n        helper(nums, target, 0, res, temp, 4); // Call the helper function to find quadruplets.\n        return res; // Return the result vector containing unique quadruplets.\n    }\n    \n    // Helper function to find unique quadruplets using recursion.\n    void helper(vector<int>& nums, long target, int start, vector<vector<int>>& res, vector<int>& temp, int numneed) {\n        // If we need more than 2 numbers, we\'re looking for the first number in the combination.\n        if (numneed != 2) {\n            for (int i = start; i < nums.size() - numneed + 1; i++) {\n                if (i > start && nums[i] == nums[i - 1]) {\n                    continue; // Skip duplicates to avoid duplicate combinations.\n                }\n                temp.push_back(nums[i]); // Add the current number to the combination.\n                helper(nums, target - nums[i], i + 1, res, temp, numneed - 1); // Recursively find the next number(s).\n                temp.pop_back(); // Remove the last number to backtrack.\n            }\n            return;\n        }\n        \n        // If we need exactly 2 numbers, perform a two-pointer approach.\n        int l = start;\n        int r = nums.size() - 1;\n        while (l < r) {\n            long sum = static_cast<long>(nums[l]) + static_cast<long>(nums[r]);\n            if (sum < target) {\n                l++;\n            } else if (sum > target) {\n                r--;\n            } else {\n                temp.push_back(nums[l]); // Add the left number to the combination.\n                temp.push_back(nums[r]); // Add the right number to the combination.\n                res.push_back(temp); // Store the valid quadruplet in the result vector.\n                temp.pop_back(); // Remove the right number to backtrack.\n                temp.pop_back(); // Remove the left number to backtrack.\n                l++;\n                r--;\n                while (l < r && nums[l] == nums[l - 1]) {\n                    l++; // Skip duplicates on the left.\n                }\n            }\n        }\n    }\n};\n```\n# JAVA\n``` \nimport java.util.ArrayList;\nimport java.util.Arrays;\nimport java.util.List;\n\npublic class Solution {\n    public List<List<Integer>> fourSum(int[] nums, int target) {\n        Arrays.sort(nums); // Sort the input array in ascending order.\n        List<List<Integer>> result = new ArrayList<>();\n        List<Integer> temp = new ArrayList<>();\n        helper(nums, (long) target, 0, result, temp, 4); // Use long data type for target.\n        return result; // Return the result list containing unique quadruplets.\n    }\n\n    private void helper(int[] nums, long target, int start, List<List<Integer>> result, List<Integer> temp, int numNeed) {\n        if (numNeed != 2) {\n            for (int i = start; i < nums.length - numNeed + 1; i++) {\n                if (i > start && nums[i] == nums[i - 1]) {\n                    continue; // Skip duplicates to avoid duplicate combinations.\n                }\n                temp.add(nums[i]); // Add the current number to the combination.\n                helper(nums, target - nums[i], i + 1, result, temp, numNeed - 1); // Recursively find the next number(s).\n                temp.remove(temp.size() - 1); // Remove the last number to backtrack.\n            }\n            return;\n        }\n\n        // If we need exactly 2 numbers, perform a two-pointer approach.\n        int l = start;\n        int r = nums.length - 1;\n        while (l < r) {\n            long total = (long) nums[l] + nums[r];\n            if (total < target) {\n                l++;\n            } else if (total > target) {\n                r--;\n            } else {\n                temp.add(nums[l]); // Add the left number to the combination.\n                temp.add(nums[r]); // Add the right number to the combination.\n                result.add(new ArrayList<>(temp)); // Store the valid quadruplet in the result list.\n                temp.remove(temp.size() - 1); // Remove the right number to backtrack.\n                temp.remove(temp.size() - 1); // Remove the left number to backtrack.\n                l++;\n                r--;\n                while (l < r && nums[l] == nums[l - 1]) {\n                    l++; // Skip duplicates on the left.\n                }\n            }\n        }\n    }\n}\n```\n# PYTHON\n```\nclass Solution:\n    def fourSum(self, nums, target):\n        def helper(nums, target, start, res, temp, num_need):\n            if num_need != 2:\n                for i in range(start, len(nums) - num_need + 1):\n                    if i > start and nums[i] == nums[i - 1]:\n                        continue  # Skip duplicates to avoid duplicate combinations.\n                    temp.append(nums[i])  # Add the current number to the combination.\n                    helper(nums, target - nums[i], i + 1, res, temp, num_need - 1)  # Recursively find the next number(s).\n                    temp.pop()  # Remove the last number to backtrack.\n                return\n\n            # If we need exactly 2 numbers, perform a two-pointer approach.\n            l, r = start, len(nums) - 1\n            while l < r:\n                total = nums[l] + nums[r]\n                if total < target:\n                    l += 1\n                elif total > target:\n                    r -= 1\n                else:\n                    temp.append(nums[l])  # Add the left number to the combination.\n                    temp.append(nums[r])  # Add the right number to the combination.\n                    res.append(temp[:])  # Store the valid quadruplet in the result list.\n                    temp.pop()  # Remove the right number to backtrack.\n                    temp.pop()  # Remove the left number to backtrack.\n                    l += 1\n                    r -= 1\n                    while l < r and nums[l] == nums[l - 1]:\n                        l += 1  # Skip duplicates on the left.\n\n        nums.sort()  # Sort the input list in ascending order.\n        res = []  # Result list to store valid quadruplets.\n        temp = []  # Temporary list to store combinations.\n        helper(nums, target, 0, res, temp, 4)  # Call the helper function to find quadruplets.\n        return res  # Return the result list containing unique quadruplets.\n```\n\n![R.jpg](https://assets.leetcode.com/users/images/2fedb1ea-428b-40ea-a6f2-166939b773d4_1696065027.8550835.jpeg)\n\n
['Backtracking', 'Python', 'C++', 'Java']