Coding Global Background
Coding Global

4Sum further optimization

Archived a year ago
3 messages
2 members
a year ago
Open in Discord
R
RotatingPanels
Copy Paster!

**Main.py**📁 ```python class Solution: def fourSum(self, nums: List[int], target: int) -> List[List[int]]: # Store the target sum and initialize the result list to store unique quadruplets self.target = target self.res = [] # If there are less than 4 numbers, it's not possible to form quadruplets if len(nums) < 4: return [] else: # Call the recursive helper function to find all possible quadruplets self.recur([], nums) return self.res def recur(self, x: List[int], y: List[int]) -> int: # Base case: If we already have 3 numbers in the current combination if len(x) == 3: # For each remaining number in the input list for n in y: # Check if adding this number to the current combination equals the target if sum(x) + n == self.target and sorted(x + [n]) not in self.res: # If it's a valid combination and not already in the result list, add it self.res.append(sorted(x + [n])) return 0 # Exit the loop once we find a valid combination return 0 # Exit when no valid combination is found else: # Recursive case: Build combinations by including each number from the input list for i, n in enumerate(y): # Call the function recursively with the current number added to the combination # and the remaining numbers excluding the current one self.recur(x + [n], y[:i] + y[i+1:]) return 0 # Return 0 after trying all possibilities ``` **Problem** I am currently attempting to solve the following problem, But my code is not computing within the given time limit. Does anyone know how I can further optimize my recursive backtracking solution without changing too much? https://leetcode.com/problems/4sum/description/ This is the link to the problem.

Replies (3)