Python | Find all triples in a list with a given sum



Examples :

  Input:  [1, 2, 3, 4, 5, 6, 7, 8, 9, 10], k = 10  Output:  [(1, 5, 4), (1, 6, 3), (1, 7, 2), (2, 5, 3)]  Input:  [12, 3, 6, 1, 6, 9], k = 24  Output:  [(12, 6, 6), (12, 9, 3)]  

Approach # 1: Naive (Using a set)
In this approach, we use two for loops. The first loop sets the first element, the other checks if the other two elements, including the first one, add up to k or not. This approach requires O (n 2 ) time complexity.

# Python3 program for finding total
Number of triplets in the list of temporary variables with a given k value

 

def findTriplets (lst, k):

triplet_count = 0

final_temp_list = []

  

  for i in range ( 0 , len (lst) - 1 ): 

 

  s = set () 

temp_list = []

  

# Add first element

temp_list.append (lst [i])

 

  curr_k = k - lst [i] 

 

for j in range (i + 1 , len (lst)): 

 

if (curr_k - lst [j]) in s: 

triplet_count + = 1

 

# Add second element

temp_list.append (lst [j])

 

# Adding a third element

temp_list.append (curr_k - lst [j])

 

# Add a tuple to the final list

final_temp_list.append ( tuple (temp_list))

temp_list.pop ( 2 )

temp_list.pop ( 1 )

  s.add (lst [j])

  

return final_temp_list

 
Driver code

lst = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ]

k = 10

print (findTriplets (lst, k))

Exit:

 [(1, 5, 4), (1, 6, 3), (1, 7, 2), (2, 5, 3)] 

Approach # 2 Using itertools
Python`s itertools module provides combined (iterable, r) function. This tool returns subsequences of length r elements from iterative input. Each time we make a combination of 3 elements and check if they add up to k or not.

# Python3 program for finding total
Number of triplets in the list with the given amount

from itertools import combinations

 

def findTriplets (lst, key):

 

def valid (val):

return sum (val) = = key

 

return list ( filter (valid, list (combinations (lst, 3 ))))

 
Driver code

lst = [ 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , 10 ]

print (findTriplets (lst, 10 ))

Output:

 [(1, 2, 7), (1, 3, 6), (1, 4, 5), (2, 3, 5)]