5 Best Ways to Find All Triplets in a List with Given Sum in Python

by

💡 Problem Formulation: Finding all distinct triplets in a list that add up to a specific sum is a common algorithmic challenge. It’s about identifying three numbers from a list whose combined total equals the target sum. For instance, given the list [1, 2, 3, 4, 5] and the sum 9, the desired output would be a list of triplets like [(2, 3, 4)], as they add up to the target sum.

Method 1: Brute Force

The brute force method entails checking all possible triplets in the array to see if their sum matches the given sum. This method uses three nested loops, hence it is straightforward but not the most efficient, with a time complexity of O(n^3).

Here’s an example:

def findTriplets(arr, sum):
    n = len(arr)
    triplets = []
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                if arr[i] + arr[j] + arr[k] == sum:
                    triplets.append((arr[i], arr[j], arr[k]))
    return sorted(triplets)

Output: [(2, 3, 4)]

This code snippet defines a function findTriplets(arr, sum) that takes a list and a sum as arguments, iterates over the list in a three-level nested loop, and appends to a result list any triplet with the given sum. Although simple, the inefficiency makes it impractical for large lists.

Method 2: Sorting and Two-Pointer Technique

This approach first sorts the list then traverses it using two pointers to find pairs for each element that add up to the required sum. Significantly more efficient than brute force with a time complexity of O(n^2).

Here’s an example:

def findTriplets(arr, sum):
    arr.sort()
    triplets = set()
    for i in range(len(arr)):
        left, right = i + 1, len(arr) - 1
        while left < right:
            current_sum = arr[i] + arr[left] + arr[right]
            if current_sum == sum:
                triplets.add((arr[i], arr[left], arr[right]))
                left += 1
                right -= 1
            elif current_sum < sum:
                left += 1
            else:
                right -= 1
    return sorted(triplets)

Output: [(2, 3, 4)]

The function findTriplets(arr, sum) sorts the list and then iterates it while adjusting the left and right pointers to find the correct triplets. The usage of a set for results ensures that only unique triplets are kept. This method balances efficiency and simplicity well.

Method 3: Hashing

Using a hash table to store the elements can optimize searching for the third component of the triplet. When iterating over the list, for each element, the problem becomes a two-sum one, which is solvable in linear time using hashing.

Here’s an example:

def findTriplets(arr, sum):
    triplets = set()
    for i in range(len(arr)-1):
        s = set()
        current_sum = sum - arr[i]
        for j in range(i + 1, len(arr)):
            if current_sum - arr[j] in s:
                triplets.add(tuple(sorted((arr[i], arr[j], current_sum - arr[j]))))
            s.add(arr[j])
    return sorted(triplets)

Output: [(2, 3, 4)]

This snippet defines a function findTriplets(arr, sum) that employs hashing to efficiently find the remaining two numbers of a triplet after picking one. While the average case time complexity is O(n^2), this method can provide significant speed-up over the previous brute force approach, especially in lists where many numbers might add up to the same sum.

Method 4: Using itertools.combinations

For a more Pythonic method, itertools.combinations can be used to generate all possible triplets, and then a filter can be applied to select only those with the desired sum. This approach avoids manual loops, although it doesn’t improve on the time complexity.

Here’s an example:

import itertools

def findTriplets(arr, sum):
    return [triplet for triplet in itertools.combinations(arr, 3) if sum(triplet) == sum]

Output: [(2, 3, 4)]

The function findTriplets(arr, sum) makes use of itertools.combinations() to generate all possible triplets, following which a list comprehension filters and returns those that add up to the given sum. It is elegant and suitable for shorter lists or when writability is prioritized over performance.

Bonus One-Liner Method 5: List Comprehension

A one-liner using list comprehension combines creating triplets and filtering them in a single statement, enabling a concise albeit inefficient solution similar in performance to brute force.

Here’s an example:

def findTriplets(arr, sum):
    return [(x, y, z) for i, x in enumerate(arr) for j, y in enumerate(arr) for k, z in enumerate(arr) if i < j < k and x + y + z == sum]

Output: [(2, 3, 4)]

The function findTriplets(arr, sum) uses list comprehension with three levels of iteration over the indexes and values of the list, combined with a condition that ensures the correct sum and distinct elements are selected. It’s extremely compact, but not recommended for performance-sensitive applications.

Summary/Discussion

  • Method 1: Brute Force. Simplest to understand. No extra space required. Extremely inefficient with time complexity O(n^3).
  • Method 2: Sorting and Two-Pointers. Balances performance and readability. O(n^2) time complexity. Requires modifying the original list order.
  • Method 3: Hashing. Offers a good trade-off between efficiency and code complexity. Best for average cases but can vary depending on input set.
  • Method 4: itertools.combinations. Very readable Pythonic solution. Time complexity remains O(n^3). Ideal for small lists or lesser concern about performance.
  • Method 5: List Comprehension. Concise one-liner. Time complexity O(n^3). Good for quick scripting or when performance is not an issue.