Coding Global Background
Coding Global

4Sum further optimization

Archived a year ago
3 messages
2 members
Created a year ago
Updated a year ago
Open in Discord
R
RotatingPanels
Script Kiddie!
Main.py📁
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 (2)