Mô phỏng thuật toán Sinh tổ hợp C(n,k)

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

Sinh mọi tổ hợp C(n,k) bằng quay lui, chọn các phần tử theo thứ tự tăng dần để không đếm trùng.

Ý tưởng

Dựng dần mảng cur; dùng biến start để phần tử sau luôn lớn hơn phần tử trước.

Từ start đến n, chọn một giá trị đưa vào cur rồi đệ quy với start mới là giá trị vừa chọn cộng một.

Khi cur đủ độ dài k thì ghi nhận một tổ hợp, rồi rút bớt phần tử cuối (quay lui) để thử giá trị khác.

Vì sao đúng

Buộc chỉ số tăng dần loại bỏ mọi hoán vị của cùng một tập, nên mỗi tổ hợp chỉ được sinh đúng một lần; cây tìm kiếm có đúng C(n,k) lá.

Mã Python

def combine(n, k, start, cur, out):
    if len(cur) == k:           # a full combination
        out.append(cur[:])      # record a copy
        return
    for i in range(start, n + 1):   # choose increasing values
        cur.append(i)           # pick value i
        combine(n, k, i + 1, cur, out)  # next start = i + 1
        cur.pop()               # backtrack: unpick i

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