Mô phỏng thuật toán Tổng tập con (đệ quy)

Subset Sum (Recursion) · Nhóm: Đệ quy

Bài toán quyết định: có tồn tại tập con của mảng có tổng đúng bằng target không, giải bằng đệ quy gồm/bỏ có cắt nhánh.

Ý tưởng

Tại mỗi chỉ số i, thử hai nhánh: GỒM a[i] (cộng vào tổng chạy) hoặc BỎ a[i], rồi đệ quy sang i+1.

Trả True ngay khi tổng chạy bằng target; cắt nhánh khi tổng chạy vượt target hoặc hết phần tử.

Khi một nhánh GỒM thất bại thì quay lui, rút phần tử vừa thêm rồi thử nhánh BỎ.

Vì sao đúng

Cây quyết định gồm/bỏ phủ mọi tập con (2ⁿ khả năng), nhưng cắt nhánh khi vượt target giúp tỉa sớm; chỉ cần một lời giải nên dừng ngay khi chạm đúng tổng, thường nhanh hơn xấu nhất nhiều.

Mã Python

def subset_sum(a, i, running, target, cur):
    if running == target:       # exact hit: cur is a solution
        return True
    if i == len(a) or running > target:
        return False            # dead end: past target or out of items
    cur.append(a[i])            # branch INCLUDE a[i]
    if subset_sum(a, i + 1, running + a[i], target, cur):
        return True
    cur.pop()                   # backtrack the include
    return subset_sum(a, i + 1, running, target, cur)  # branch EXCLUDE a[i]

Mở trang để xem mô phỏng từng bước và xuất slide bài giảng.