บทนำ
โจทย์ Subset Sum Problem คือการหาชุดย่อย (subset) ทุกชุดจากลิสต์ที่มีผลรวมเท่ากับค่าเป้าหมาย s สามารถแก้ได้ด้วยการสร้างคอมบิเนชันทุกความยาวแล้วตรวจสอบผลรวม
วิธีการ: ใช้ itertools.combinations
โมดูล itertools มีฟังก์ชัน combinations() ที่สร้างคอมบิเนชันทุกชุดได้อย่างมีประสิทธิภาพ
ตัวอย่างโค้ด
from itertools import combinations
def subset_sum(arr, target):
"""คืนลิสต์ของ subset ทุกชุดที่มีผลรวมเท่ากับ target"""
result = []
n = len(arr)
# ลองทุกความยาวของ subset ตั้งแต่ 0 ถึง n
for r in range(n + 1):
for combo in combinations(arr, r):
if sum(combo) == target:
result.append(list(combo))
return result
# ทดสอบ
my_list = [21, 32, 56, 78, 45, 99, 0]
target = 53
print(f"ลิสต์ต้นทาง: {my_list}")
print(f"ค่าเป้าหมาย: {target}")
print("Subset ที่มีผลรวมเท่ากับเป้าหมาย:")
subsets = subset_sum(my_list, target)
for subset in subsets:
print(f" {subset} -> sum = {sum(subset)}")
ผลลัพธ์
ลิสต์ต้นทาง: [21, 32, 56, 78, 45, 99, 0]
ค่าเป้าหมาย: 53
Subset ที่มีผลรวมเท่ากับเป้าหมาย:
[21, 32] -> sum = 53
[21, 32, 0] -> sum = 53
บันทึกประสิทธิภาพ
- ความซับซ้อนเวลา: O(2^n) - เหมาะกับลิสต์ขนาดเล็ก (n ≤ 20)
- สำหรับลิสต์ใหญ่ ควรใช้ Dynamic Programming หรือ Meet-in-the-Middle
- หากมีค่าลบในลิสต์ จำนวน subset อาจมากมาย
วิธีปรับปรุงประสิทธิภาพ (Pruning)
def subset_sum_optimized(arr, target):
"""เวอร์ชันที่เร็วกว่าด้วยการ sort และ pruning"""
arr = sorted(arr)
result = []
def backtrack(start, path, current_sum):
if current_sum == target:
result.append(path[:])
return
if current_sum > target:
return
for i in range(start, len(arr)):
# ข้ามค่าซ้ำเพื่อไม่ให้ subset ซ้ำ
if i > start and arr[i] == arr[i-1]:
continue
path.append(arr[i])
backtrack(i + 1, path, current_sum + arr[i])
path.pop()
backtrack(0, [], 0)
return result
สรุป
วิธี itertools.combinations เข้าใจง่ายและเขียนสั้น เหมาะสำหรับข้อมูลเล็กและการเรียนรู้ สำหรับระบบจริงที่ต้องการประสิทธิภาพ ควรใช้ backtracking พร้อม pruning หรือ Dynamic Programming
