ปัญหา: กำหนด Array `nums` และ Target `k` นับจำนวน Subsets ที่ Sum = k (Mod 10⁹+7)
Subset = เลือก Elements ใดๆ (Order ไม่สำคัญ, ไม่ซ้ำ Element เดียวกัน)
อัลกอริทึม: 0/1 Knapsack DP (Counting Ways)
DP[i][j] = จำนวนวิธีทำ Sum = j ด้วย Elements แรก i ตัว
Optimization: 1D Array `dp[j]` Iterate j จาก k ลง 0 (ป้องกันใช้ Element ซ้ำ)
การติดตั้ง
class Solution:
def solve(self, nums, k):
MOD = 10**9 + 7
dp = [0] * (k + 1)
dp[0] = 1 # Empty Subset = Sum 0 (1 Way)
for num in nums:
# Iterate BACKWARDS เพื่อ 0/1 Knapsack (ใช้แต่ละ Item Max 1 ครั้ง)
for j in range(k, num - 1, -1):
dp[j] = (dp[j] + dp[j - num]) % MOD
return dp[k]
# Test
ob = Solution()
nums = [2, 3, 4, 5, 7]
k = 7
print(ob.solve(nums, k)) # 3: [2,5], [3,4], [7]
คำอธิบาย
dp[0] = 1: Base Case - Empty Subset Sum = 0 (1 Way)Loop `num` ใน `nums`: พิจารณาเอา `num` ไปรวม Subset เดิมๆ
Loop `j` จาก `k` ลง `num`: Backwards สำคัญ! ป้องกันใช้ `num` ซ้ำในรอบเดียวกัน
`dp[j] += dp[j-num]`: เพิ่มวิธีที่ทำ Sum j-num แล้วมาบวก num
Trace ตัวอย่าง
nums = [2, 3, 4, 5, 7], k = 7
dp[0] = 1
num=2: j=7..2
dp[2] += dp[0] = 1 → [2]
num=3: j=7..3
dp[3] += dp[0] = 1 → [3]
dp[5] += dp[2] = 1 → [2,3]
num=4: j=7..4
dp[4] += dp[0] = 1 → [4]
dp[6] += dp[2] = 1 → [2,4]
dp[7] += dp[3] = 1 → [3,4] ✓
num=5: j=7..5
dp[5] += dp[0] = 1 → [5] (เพิ่มจาก [2,3] รวม 2 ways)
dp[7] += dp[2] = 1 → [2,5] ✓ (รวม 2 ways)
num=7: j=7
dp[7] += dp[0] = 1 → [7] ✓ (รวม 3 ways)
Result: dp[7] = 3
Complexity
- Time: O(n × k) где n = len(nums)
- Space: O(k)
Variations
# 1. Unbounded Knapsack (ใช้ Element ได้หลายครั้ง)
for num in nums:
for j in range(num, k+1): # FORWARDS
dp[j] = (dp[j] + dp[j-num]) % MOD
# 2. Return All Subsets (ไม่ใช่ Count)
def find_subsets(nums, k):
result = []
def backtrack(start, path, total):
if total == k:
result.append(path[:])
return
for i in range(start, len(nums)):
if total + nums[i] <= k:
backtrack(i+1, path+[nums[i]], total+nums[i])
backtrack(0, [], 0)
return result
# 3. With Negative Numbers → Offset DP Array
# 4. Large k (Meet-in-the-Middle: Split Array Half, O(2^(n/2)))
Constraints ทั่วไป: n ≤ 1000, k ≤ 1000-10000, Mod 10⁹+7
