4Sum further optimization
Archived a year ago
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.
