Cho danh sách số, tìm tất cả bộ ba (triplet) có tổng bằng giá trị cho trước.
Cách 1: Vòng lặp + set (O(n²))
Với mỗi phần tử i, dùng set lưu các phần tử đã thấy, tìm cặp (j, k) sao cho tổng bằng mục tiêu.
def SumTriplets(listA, target):
res = []
for i in range(len(listA) - 1):
s = set()
tmp = [listA[i]]
current_sum = target - listA[i]
for j in range(i+1, len(listA)):
if (current_sum - listA[j]) in s:
tmp.append(listA[j])
tmp.append(current_sum - listA[j])
res.append(tuple(tmp))
tmp.pop()
tmp.pop()
s.add(listA[j])
return res
listA = [11,12,13,14,15,16,17,18,19,20]
print("Triplets sum 40:", SumTriplets(listA, 40))
# [(11, 15, 14), (11, 16, 13), (11, 17, 12), (12, 15, 13)]
Cách 2: itertools.combinations + filter
Tạo tất cả tổ hợp 3 phần tử, lọc theo tổng.
from itertools import combinations
listA = [11,12,13,14,15,16,17,18,19,20]
res = list(filter(lambda x: sum(x)==40, combinations(listA, 3)))
print("Triplets sum 40:", res)
# [(11, 12, 17), (11, 13, 16), (11, 14, 15), (12, 13, 15)]