หา Triplets ที่ Sum เท่ากับ Target
กำหนดลิสต์ตัวเลขและ Target Sum หา Triplets ทั้งหมด (ไม่ซ้ำกัน) ที่ผลรวมเท่ากับ Target
วิธีที่ 1: Two-pointer หลังเรียง (O(N²))
def three_sum(arr, target):
arr.sort()
res = []
n = len(arr)
for i in range(n-2):
if i>0 and arr[i]==arr[i-1]: continue
l, r = i+1, n-1
while l < r:
s = arr[i] + arr[l] + arr[r]
if s == target:
res.append((arr[i], arr[l], arr[r]))
l += 1; r -= 1
while lวิธีที่ 2: ใช้ itertools.combinations + filter (สำหรับ N เล็ก)
from itertools import combinations
arr = [11,12,13,14,15,16,17,18,19,20]
target = 40
triplets = list(filter(lambda c: sum(c)==target, combinations(arr,3)))
print(triplets)
# [(11,12,17), (11,13,16), (11,14,15), (12,13,15)]
