มี Array nums และค่า Sum ต้องเช็คว่าบวก Element ใน nums (ใช้ซ้ำได้) ได้ Sum หรือไม่
เช่น Input nums = [2, 3, 5], sum = 28 Output True (5*5 + 3*1 = 28? Wait 5*5=25+3=28)
ขั้นตอนแก้ (Unbounded Knapsack / Coin Change DP):
- DP Table ขนาด MAX (1000) เก็บว่าทำ Sum ได้หรือไม่
- DP[0] = True
- สำหรับแต่ละ Coin: Update DP[j+coin] = True ถ้า DP[j] = True
ตัวอย่างโค้ด
MAX = 1000
table = [0] * MAX
def util(nums):
table[0] = 1
nums.sort()
for i in range(len(nums)):
val = nums[i]
if table[val]:
continue
for j in range(MAX - val):
if table[j]:
table[j + val] = 1
def solve(nums, sum):
util(nums)
if table[sum]:
return True
return False
nums = [2, 3, 5]
sum = 28
print(solve(nums, sum))
Input
[2, 3, 5], 28
Output
True
