5 Best Ways to Find the Number of Distinct Quadruples that Form Target Sum in Python

Rate this post

πŸ’‘ Problem Formulation: Given a list of integers and a target sum, the goal is to determine the number of distinct quadruples (groups of four numbers) within the list that add up to the target sum. For example, given the list [1, 0, -1, 0, -2, 2] and a target sum of 0, the desired output would be 3, representing the three distinct quadruples (-2, -1, 1, 2), (-2, 0, 0, 2), and (-1, 0, 0, 1) that add up to 0.

Method 1: Brute Force Approach

This method involves checking all possible quadruples in the list to see which ones sum up to the target. The function signature might be something like brute_force_quadruples(nums, target). While straightforward, this method is limited by its O(n^4) time complexity, making it impractical for large lists.

Here’s an example:

def brute_force_quadruples(nums, target):
    n = len(nums)
    result = set()
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                for l in range(k+1, n):
                    if nums[i] + nums[j] + nums[k] + nums[l] == target:
                        result.add(tuple(sorted((nums[i],nums[j],nums[k],nums[l]))))
    return len(result)

print(brute_force_quadruples([1, 0, -1, 0, -2, 2], 0))

Output: 3

This code snippet works by iterating over every combination of four different indices in the list and checking if the corresponding numbers sum to the target. Results are stored in a set to ensure distinct quadruples, and the length of the set is returned as the output.

Method 2: Using Two-Pointer Technique

The two-pointer technique is applied after sorting the list. For each pair of numbers, we use another pair of pointers to find complementary pairs that complete the quadruple sum to the target. This method is more efficient with a complexity of O(n^3), reflected in the function two_pointer_quadruples(nums, target).

Here’s an example:

def two_pointer_quadruples(nums, target):
    nums.sort()
    n = len(nums)
    result = set()
    for i in range(n - 3):
        for j in range(i + 1, n - 2):
            left, right = j + 1, n - 1
            while left < right:
                total = nums[i] + nums[j] + nums[left] + nums[right]
                if total == target:
                    result.add((nums[i], nums[j], nums[left], nums[right]))
                    left += 1
                    right -= 1
                elif total < target:
                    left += 1
                else:
                    right -= 1
    return len(result)

print(two_pointer_quadruples([1, 0, -1, 0, -2, 2], 0))

Output: 3

This code first sorts the list then iteratively fixes two numbers and searches for complementary pairs using the two-pointer approach. Keeping the list sorted ensures that the two pointers yield only non-repeating results, which are inserted into a set.

Method 3: Hashing for Complementary Pairs

By using a hashmap, we can store sums of all possible pairs and their corresponding indices. Later, we can search for pairs within this hashmap that would complement to the target sum. This method’s complexity is generally around O(n^2) and would be called as hashmap_quadruples(nums, target).

Here’s an example:

from collections import defaultdict

def hashmap_quadruples(nums, target):
    n = len(nums)
    two_sum_map = defaultdict(list)
    result = set()
    for i in range(n - 1):
        for j in range(i + 1, n):
            current_sum = nums[i] + nums[j]
            complement = target - current_sum
            if complement in two_sum_map:
                for (k, l) in two_sum_map[complement]:
                    if k != i and k != j and l != i and l != j:
                        quad = tuple(sorted((nums[i], nums[j], nums[k], nums[l])))
                        result.add(quad)
            two_sum_map[current_sum].append((i, j))
    return len(result)

print(hashmap_quadruples([1, 0, -1, 0, -2, 2], 0))

Output: 3

In this approach, the code creates a hashmap of all possible two-number sums along with their indices. When iterating over pairs of numbers, it looks for their complement in the hashmap. If found, it stores the quadruple in a set after checking for index overlaps.

Method 4: Hashing with Early Stopping

The early stopping variation of the hashing method organizes the pairs of sums and stops the iteration whenever it encounters pairs that cannot contribute to a new distinct quadruple. The function would have a similar specification, such as hashmap_early_stopping_quadruples(nums, target). It’s more efficient as it avoids unnecessary processing.

Here’s an example:

def hashmap_early_stopping_quadruples(nums, target):
    nums.sort()
    n = len(nums)
    two_sum_map = defaultdict(list)
    result = set()
    for i in range(n - 1):
        for j in range(i + 1, n):
            current_sum = nums[i] + nums[j]
            complement = target - current_sum
            if complement in two_sum_map:
                for (k, l) in two_sum_map[complement]:
                    if k > j:
                        break
                    quad = tuple(sorted((nums[i], nums[j], nums[k], nums[l])))
                    result.add(quad)
            two_sum_map[current_sum].append((i, j))
    return len(result)

print(hashmap_early_stopping_quadruples([1, 0, -1, 0, -2, 2], 0))

Output: 3

This method improves the hashmap approach by sorting the list and stopping the iteration through the hashmap if it encounters indices larger than the current index pairs. This optimizes performance while ensuring no duplicates.

Bonus One-Liner Method 5: Using itertools combinations

This one-liner uses Python’s itertools module to create all possible quadruples and filters them to count the distinct quadruples that sum up to the target. Here’s a compact but not very efficient method itertools_combinations_quadruples(nums, target), which achieves the goal using functional programming techniques.

Here’s an example:

from itertools import combinations

def itertools_combinations_quadruples(nums, target):
    return len(set(quad for quad in combinations(nums, 4) if sum(quad) == target))

print(itertools_combinations_quadruples([1, 0, -1, 0, -2, 2], 0))

Output: 3

The one-liner is concise and leverages the power of Python’s standard libraries. It creates all possible quadruples using combinations(nums, 4), filters by sum, and casts the result to a set to deduplicate, ultimately returning the count.

Summary/Discussion

  • Method 1: Brute Force. Simple implementation. Time-consuming for large datasets due to O(n^4) complexity.
  • Method 2: Two-Pointer Technique. More efficient than brute force with O(n^3) complexity. Requires sorting, which may be a drawback for unsortable data.
  • Method 3: Hashing for Complementary Pairs. Offers improved performance with ~O(n^2) complexity. Requires extra memory for the hashmap.
  • Method 4: Hashing with Early Stopping. Increases efficiency by minimizing unnecessary checks. Requires sorted list and more complex logic.
  • Method 5: Using itertools combinations. Elegant one-liner, but not as performance-optimized as other methods. Best suited for small to medium-sized datasets.