Mô phỏng thuật toán Sinh tập con (quay lui)

Subsets (Backtracking) · Nhóm: Đệ quy

Sinh mọi tập con của một tập bằng quay lui: tại mỗi chỉ số quyết định GỒM hay BỎ phần tử tương ứng.

Ý tưởng

Duyệt lần lượt từng chỉ số của tập gốc.

Nhánh A: thêm phần tử hiện tại vào cur rồi đệ quy sang chỉ số kế; nhánh B: bỏ phần tử rồi đệ quy tiếp.

Khi chỉ số chạm cuối, mảng cur hiện thời là một tập con hoàn chỉnh, ghi nhận rồi quay lui.

Vì sao đúng

Cây quyết định gồm/bỏ có đúng 2ⁿ lá, mỗi lá ứng với một tập con; hai lựa chọn nhị phân ở mỗi mức phủ trọn mọi tập con kể cả tập rỗng, không trùng, không sót.

Mã Python

def subsets(nums, index, cur, out):
    if index == len(nums):      # all decisions made
        out.append(cur[:])      # record one subset (a copy)
        return
    cur.append(nums[index])     # decision A: include nums[index]
    subsets(nums, index + 1, cur, out)
    cur.pop()                   # backtrack: undo the include
    subsets(nums, index + 1, cur, out)  # decision B: exclude it

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