Subset Sum Problem ใน Python

โจทย์: กำหนดเซ็ตตัวเลขไม่ติดลบ และค่า Target Sum หาว่ามี Subset ที่ผลรวมเท่ากับ Target หรือไม่

ตัวอย่าง

Set = [2, 14, 6, 22, 4, 8], Target = 10
Output: True (Subset: [2, 4, 4] หรือ [6, 4] หรือ [2, 8])

วิธีที่ 1: Recursive (Naive) - Exponential

def subset_sum_recursive(arr, n, target):
    # Base cases
    if target == 0:
        return True
    if n == 0:
        return False
    
    # ถ้าตัวสุดท้าย > target ข้ามไป
    if arr[n-1] > target:
        return subset_sum_recursive(arr, n-1, target)
    
    # ลองรวม หรือ ไม่รวม ตัวสุดท้าย
    return (subset_sum_recursive(arr, n-1, target) or
            subset_sum_recursive(arr, n-1, target - arr[n-1]))

วิธีที่ 2: Dynamic Programming - Pseudo-polynomial O(n×target)

def subset_sum_dp(arr, target):
    n = len(arr)
    # dp[i][j] = สามารถทำ Sum j ได้จาก arr[:i] หรือไม่
    dp = [[False] * (target + 1) for _ in range(n + 1)]
    
    # Sum 0 ทำได้เสมอ (Empty subset)
    for i in range(n + 1):
        dp[i][0] = True
    
    for i in range(1, n + 1):
        for j in range(1, target + 1):
            if arr[i-1] > j:
                dp[i][j] = dp[i-1][j]
            else:
                dp[i][j] = dp[i-1][j] or dp[i-1][j - arr[i-1]]
    
    return dp[n][target]

# ทดสอบ
arr = [2, 14, 6, 22, 4, 8]
target = 10
print(subset_sum_dp(arr, target))  # True

วิธีที่ 3: Space Optimized DP O(target)

def subset_sum_optimized(arr, target):
    dp = [False] * (target + 1)
    dp[0] = True
    
    for num in arr:
        for j in range(target, num - 1, -1):  # Backward เพื่อไม่ใช้ค่ารอบเดียวกัน
            if dp[j - num]:
                dp[j] = True
    
    return dp[target]

print(subset_sum_optimized([2, 14, 6, 22, 4, 8], 10))  # True

หมายเหตุ: โค้ดต้นฉบับส่วน Dynamic Approach ผิด (เป็นโค้ด Activity Selection) โค้ดข้างต้นเป็น DP จริงสำหรับ Subset Sum