Kiểm tra tổng mục tiêu có tạo được từ mảng (có lặp) không (Python)

Bài toán: Cho mảng nums và mục tiêu sum. Mỗi phần tử có thể dùng nhiều lần. Kiểm tra có thể tạo ra sum không.

Dynamic Programming (Unbounded Knapsack / Coin Change)

dp[x] = True nếu có thể tạo tổng x.
Khởi tạo dp[0] = True. Với mỗi val trong nums, cập nhật: dp[j+val] |= dp[j].

Triển khai Python

MAX = 1000
table = [0] * MAX

def util(nums):
    table[0] = 1
    nums.sort()
    for val in nums:
        if table[val]:
            continue
        for j in range(MAX - val):
            if table[j]:
                table[j + val] = 1

def solve(nums, target):
    util(nums)
    return table[target] != 0

# Test
print(solve([2, 3, 5], 28))   # True: 5*5 + 3*1 = 28? 5+5+5+5+3+3+2=28
print(solve([2, 4, 6], 7))    # False: chỉ tạo được số chẵn
print(solve([3, 5], 7))       # False: 3,5,6,8,9,10... không có 7

Kết quả

True

Giải thích

• table kích thước MAX (1000) lưu trạng thái có tạo được tổng hay không.
• Duyệt nums đã sort. Với mỗi val, cập nhật các tổng lớn hơn.
• Bỏ qua nếu table[val] đã True (đã tạo được).
• Độ phức tạp: O(n × MAX) time, O(MAX) space.
• Lưu ý: MAX phải ≥ target. Code dùng biến global table.