4Sum

Try every combination of four indices and check if they sum to the target. Use a set to avoid duplicate quadruplets.

1. 1Four nested loops over indices a < b < c < d.
2. 2If the sum equals target, add the sorted quadruplet to a result set.
3. 3Return the deduplicated list.

Why it's not optimal: O(n⁴) is far too slow. Sorting + fixing two outer loops + two-pointer inner loop reduces this to O(n³).

def fourSum(nums, target):
    res = set()
    n = len(nums)
    for a in range(n):
        for b in range(a+1, n):
            for c in range(b+1, n):
                for d in range(c+1, n):
                    if nums[a]+nums[b]+nums[c]+nums[d] == target:
                        quad = tuple(sorted([nums[a],nums[b],nums[c],nums[d]]))
                        res.add(quad)
    return [list(q) for q in res]

Sort the array. Fix two outer indices i and j, then use two pointers L and R on the remaining subarray. Skip duplicate values at every level to avoid duplicate quadruplets.

1. 1Sort the array.
2. 2Outer loop: fix i, skip duplicates.
3. 3Inner loop: fix j = i+1, skip duplicates.
4. 4Two-pointer L = j+1, R = n-1. Move based on sum vs target. After match, skip duplicate L and R values.