Find Triplets with Given Sum in List in Python - Simple Guide

To find triplets with a given sum in a Python list, first sort the list, then use a loop with two pointers to check pairs that complete the triplet sum. This approach uses O(n^2) time and avoids checking all combinations directly.

Syntax

The common pattern to find triplets with a given sum involves these steps:

• Sort the list to enable two-pointer technique.
• Loop through each element as the first element of the triplet.
• Use two pointers starting from the next element and the end of the list to find pairs that sum with the first element to the target.

This method efficiently finds all triplets without duplicates.

python

def find_triplets(arr, target_sum):
    arr.sort()
    triplets = []
    for i in range(len(arr) - 2):
        left = i + 1
        right = len(arr) - 1
        while left < right:
            current_sum = arr[i] + arr[left] + arr[right]
            if current_sum == target_sum:
                triplets.append((arr[i], arr[left], arr[right]))
                left += 1
                right -= 1
            elif current_sum < target_sum:
                left += 1
            else:
                right -= 1
    return triplets

Example

This example shows how to find all triplets in a list that add up to 12.

python

def find_triplets(arr, target_sum):
    arr.sort()
    triplets = []
    for i in range(len(arr) - 2):
        left = i + 1
        right = len(arr) - 1
        while left < right:
            current_sum = arr[i] + arr[left] + arr[right]
            if current_sum == target_sum:
                triplets.append((arr[i], arr[left], arr[right]))
                left += 1
                right -= 1
            elif current_sum < target_sum:
                left += 1
            else:
                right -= 1
    return triplets

numbers = [1, 4, 45, 6, 10, 8]
target = 12
result = find_triplets(numbers, target)
print(result)

Output

[(4, 6, 2)]

Common Pitfalls

Common mistakes when finding triplets include:

• Not sorting the list first, which breaks the two-pointer logic.
• Not moving pointers correctly, causing infinite loops or missed triplets.
• Not handling duplicates if unique triplets are required.

Always ensure the list is sorted and pointers move based on comparison with the target sum.

python

def wrong_find_triplets(arr, target_sum):
    triplets = []
    for i in range(len(arr)):
        for j in range(i + 1, len(arr)):
            for k in range(j + 1, len(arr)):
                if arr[i] + arr[j] + arr[k] == target_sum:
                    triplets.append((arr[i], arr[j], arr[k]))
    return triplets

# This works but is slow (O(n^3)) and inefficient

# Correct approach uses sorting and two pointers as shown before.

Quick Reference

Tips for finding triplets with given sum:

• Sort the list first.
• Use a loop for the first element.
• Use two pointers for the other two elements.
• Move pointers based on sum comparison.
• Handle duplicates if needed.

Key Takeaways

Sort the list to use the two-pointer technique efficiently.

Use a loop for the first element and two pointers for the other two.

Move pointers inward based on whether the current sum is less or more than the target.

Avoid triple nested loops for better performance (O(n^2) instead of O(n^3)).

Handle duplicates if you want unique triplets only.