حل سوالات استخدامی سایت leetcode.com

Problem: No. 18. 4Sum #medium

Condition:
Given an array nums of n integers, return an array of all unique quadruples [nums[a], nums[b], nums[c], nums[d]] such that:
0 <= a, b, c, d < n
a, b, c and d are different.
nums[a] + nums[b] + nums[c] + nums[d] == target
You can return the response in any order.

Solution:

    nums.sort()
    results = []
    self.findNsum(nums, target, 4, [], results)
    return results

def findNsum(self, nums, target, N, result, results):
    if len(nums) < N or N < 2: return

    # solve 2-sum
    if N == 2:
        l,r = 0,len(nums)-1
        while l < r:
            if nums[l] + nums[r] == target:
                results.append(result + [nums[l], nums[r]])
                l += 1
                r -= 1
                while l < r and nums[l] == nums[l - 1]:
                    l += 1
                while r > l and nums[r] == nums[r + 1]:
                    r -= 1
            elif nums[l] + nums[r] < target:
                l += 1
            else:
                r -= 1
    else:
        for i in range(0, len(nums)-N+1): # careful about range
            if target < nums[i]*N or target > nums[-1]*N: # take advantages of sorted list
                break
            if i == 0 or i > 0 and nums[i-1] != nums[i]: # recursively reduce N
                self.findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)
    return

Explanation:
Sorting:

First the nums array is sorted. Sorting makes it easier to handle duplicates and speeds up execution using binary search.
Recursive function findNsum:

The findNsum function recursively finds combinations whose sum is equal to the given target. Depending on the value of N, it handles different cases:
For N = 2: This is the "Two Sum" subtask. We use two pointers (l and r) to find pairs of numbers in the array that add up to target.
If the current pair of numbers nums[l] and nums[r] sums to target, add this pair to the results.
We move the pointers left and right, skipping duplicates to avoid repeated combinations.
For N > 2: The function calls itself recursively, decrementing N by 1 and continuing to search for combinations among the remaining elements of the array. We also check if the current element and its combinations are within a valid range (for optimization).
Conditions for exiting recursion:

If the length of the array is less than N or N is less than 2, the function terminates execution, since there is no point in further searching for combinations.
We use conditions to stop execution if the current element is too large or too small to achieve the target value for a given number of elements (N).
Unique combinations:

To avoid duplicates, we check whether the current element is unique compared to previous ones.
Collection of results:

The results for each call to the findNsum function are added to the results list.



#interview #LeetCode

🆔 @Python4all_pro