Khóa học Python từ Cơ bản đến Nâng cao

Bài 11.2 - Bài toán Subset Sum trong Python

Trong bài học này, chúng ta sẽ cùng nhau tìm hiểu cách giải bài toán Subset Sum — một trong những bài toán nền tảng trong nhóm bài toán NP-complete.

Đề bài

Cho một danh sách các số nguyên dương nums và một số nguyên dương target. Hãy xác định xem liệu có tồn tại một tập con của nums có tổng bằng target hay không.

💡 Ý tưởng

Chúng ta sẽ sử dụng Quy hoạch động (Dynamic Programming) để xây dựng một bảng 2 chiều dp, trong đó dp[i][j] thể hiện:

Có thể chọn ra tập con từ nums[0..i-1] sao cho tổng là j hay không?

• Nếu không chọn phần tử thứ i-1: kế thừa giá trị từ dp[i-1][j].
• Nếu chọn phần tử thứ i-1: kiểm tra dp[i-1][j - nums[i-1]].

✅ Cài đặt bằng Python

def subset_sum(nums, target):
    n = len(nums)
    dp = [[False] * (target + 1) for _ in range(n + 1)]

    # Tổng bằng 0 thì luôn luôn có thể chọn tập rỗng
    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 j < nums[i - 1]:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i - 1]]

    return dp[n][target]

🧪 Ví dụ minh hoạ

Ví dụ 1:

nums = [3, 34, 4, 12, 5, 2]
target = 9
print(subset_sum(nums, target))  # Kết quả: True

Giải thích: Có tập con [4, 5] hoặc [3, 2, 4] có tổng bằng 9.

Ví dụ 2:

nums = [1, 2, 3, 7]
target = 6
print(subset_sum(nums, target))  # Kết quả: True

Giải thích: Có thể chọn [1, 2, 3] để có tổng 6.

Ví dụ 3:

nums = [2, 4, 6]
target = 5
print(subset_sum(nums, target))  # Kết quả: False

Giải thích: Không có tổ hợp nào của [2, 4, 6] có tổng bằng 5.

🔍 Phân tích độ phức tạp

• Thời gian: O(n × target), với n là độ dài của danh sách nums.
• Không gian: O(n × target), vì ta sử dụng mảng 2 chiều để lưu trạng thái.

🧠 Cải tiến

Ta có thể tối ưu không gian bằng cách dùng một mảng 1 chiều dp[target + 1], cập nhật từ phải qua trái để không ghi đè dữ liệu.

def subset_sum_optimized(nums, target):
    dp = [False] * (target + 1)
    dp[0] = True

    for num in nums:
        for j in range(target, num - 1, -1):
            dp[j] = dp[j] or dp[j - num]

    return dp[target]

✨ Tổng kết

Bài toán Subset Sum không chỉ là một thử thách thú vị mà còn là bước khởi đầu quan trọng để học về tư duy quy hoạch động. Bằng cách hiểu rõ cách tạo và cập nhật bảng dp, bạn sẽ có nền tảng tốt để tiếp cận những bài toán lớn hơn như Partition Equal Subset Sum, Knapsack Problem, và nhiều bài toán nâng cao khác.