Given a list of integers, write a Python program to find all triplets that sum up to given integer ‘k’.
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 set]
In this approach, we use two for loops. The first loop sets first element, another to check whether other two elements including first sums up to k or not. This approach takes O[n2] time complexity.
def findTriplets[lst, k]:
triplet_count =
0
final_temp_list =[]
for i in range[0, len[lst]-1]:
s = set[]
temp_list = []
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
temp_list.append[lst[j]]
temp_list.append[curr_k - lst[j]]
final_temp_list.append[tuple[temp_list]]
temp_list.pop[2]
temp_list.pop[1]
s.add[lst[j]]
return final_temp_list
lst = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
k = 10
print[findTriplets[lst, k]]
Output:
[[1, 5, 4], [1, 6, 3], [1, 7, 2], [2, 5, 3]]
Approach #2 : Using itertools
Python itertools module provide combination[iterable, r] function. This tool returns the r length subsequences of elements from the input iterable. Every time we make a combination of 3 elements and check if they sums up to k or not.
from itertools import combinations
def findTriplets[lst, key]:
def valid[val]:
return
sum[val] == key
return list[filter[valid, list[combinations[lst, 3]]]]
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]]