Tổ hợp

Nguồn: CLUE OJ – Chương 20: Quay lui (Backtracking) Độ khó: Dễ Quay lui Tổ hợp

Đề bài

Cho 2 số nguyên $N$ và $K$ $(1 \le K \le N \le 20)$. Hãy liệt kê tất cả các tổ hợp $K$ số có thể được chọn từ phạm vi $1 \to N$. Các số được in ra theo thứ tự từ điển tăng dần.

Input: gồm 2 số nguyên $N$ và $K$.

Output: in ra các tập con thỏa mãn, mỗi tập con trên một dòng.

Ví dụ 1 – input

4 2

Ví dụ 1 – output

1 2
1 3
1 4
2 3
2 4
3 4

Ví dụ 2 – input

4 3

Ví dụ 2 – output

1 2 3
1 2 4
1 3 4
2 3 4

Lời mở đầu

Khác với chỉnh hợp, tổ hợp không phân biệt thứ tự: $\{1, 2\}$ và $\{2, 1\}$ là một. Cách tự nhiên để mỗi tập chỉ xuất hiện một lần là luôn viết nó theo thứ tự tăng dần. Mình đi 2 cách quay lui: cách 1 "chọn hay không chọn từng số", cách 2 "chọn số cho từng vị trí, số sau lớn hơn số trước" kèm một cận trên giúp cây không có nhánh thừa.

Dành cho học viên · Ưu tiênNộp bài trên hệ thống CLUE OJ

Link này chỉ học viên đã tham gia tổ chức mới vào được. Học viên nên ưu tiên nộp ở đây vì sẽ được chấm nhanh hơn.

Nộp bài trên CLUE OJ

Lộ trình lời giải, bấm vào từng phần để nhảy tới:

Bộ test3 mức nÝ tưởngx tăng dầnCách 1chọn / không chọnCách 2cận n − k + i

Bộ testBộ test chính thức có gì?

Bộ test có 100 test. Đề không chia subtask, nhưng $n$ tăng dần theo 3 nhóm rõ rệt nên mình chia 3 mức (2 cột cuối là số test đúng của 2 cách, chạy thật):

Mức	Các test	n	k	Số dòng $C_n^k$	Test có k = n	Cách 1	Cách 2
1	1 – 30	1 … 8	1 … 8	1 … 70	8	30/30	30/30
2	31 – 70	9 … 15	1 … 15	1 … 5.005	2	40/40	40/40
3	71 – 100	16 … 20	2 … 19	1 … 184.756	2	30/30	30/30

Test lớn nhất là $n = 20, k = 10$ với $C_{20}^{10} = 184.756$ dòng (khoảng 5.081 KB output). Có cả những test $k = n$ (chỉ 1 dòng) – code phải xử lý được trường hợp này.

Ý tưởngSố sau luôn lớn hơn số trước

Ta điền $x_1 < x_2 < \cdots < x_k$. Ở vị trí $i$, số $x_i$ phải lớn hơn $x_{i-1}$ (đặt $x_0 = 0$). Nhưng nó cũng không được quá lớn: sau nó còn $k - i$ vị trí cần $k - i$ số lớn hơn nó, nên

Khoảng giá trị của $x_i$

$$x_{i-1} + 1 \;\le\; x_i \;\le\; n - k + i$$ Ví dụ $n = 4, k = 2$: $x_1$ chỉ chạy từ 1 tới $4 - 2 + 1 = 3$ (chọn $x_1 = 4$ thì không còn số nào cho $x_2$).

Thử từ nhỏ tới lớn ở mọi vị trí nên kết quả ra đúng thứ tự từ điển. Em nhập $n, k$ rồi bấm Tiếp; nút đỏ ✗ là giá trị bị cận trên $n - k + i$ chặn lại, không cần thử:

n = k =

Ví dụ nhanh:

Cách 1Chọn hay không chọn từng số

Cách nghĩ quen thuộc của bài "tập con": xét lần lượt các số $v = 1, 2, \ldots, n$, mỗi số có 2 nhánh – chọn hoặc không chọn. Đủ $k$ số thì in. Vì nhánh "chọn" được đi trước, các tập chứa số nhỏ hơn được in trước → đúng thứ tự từ điển.

C++▶ Chạy tay từng dòng codeCách 1: mỗi số có 2 nhánh chọn / không chọn, đủ k số thì in.

Dữ liệu vào (stdin) – sửa thoải mái4 2

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• Phải kiểm tra chon.size() == k trước v > n: tổ hợp có chứa số $n$ chỉ đủ $k$ số khi đã gọi tới Try(n + 1).
• chon.pop_back() là bước quay lui: bỏ $v$ ra rồi đi nhánh "không chọn $v$".

Không gian$O(n)$

Thời gian$O(2^n + k \cdot C_n^k)$

Kết quả chạy thật: C++: đúng 100/100 test, test chậm nhất chạy 0.078 giây. Bản Python: Python: đúng 100/100 test, test chậm nhất chạy 0.301 giây.

Cây nhị phân có tới $2^{n}$ nhánh, nhiều nhánh đi tới cuối mà không đủ $k$ số (công thừa). Với $n = 20$ thì $2^{20} \approx 10^6$, vẫn chạy rất nhanh.

Cách 2Chọn số cho từng vị trí, có cận trên

C++▶ Chạy tay từng dòng codeCách 2: x[i] chạy từ x[i-1] + 1 tới n − k + i, không có nhánh cụt.

Dữ liệu vào (stdin) – sửa thoải mái4 2

Dữ liệu mẫu:

ChậmVừaNhanhRất nhanh

• x[0] = 0 (biến toàn cục) nên vị trí 1 bắt đầu thử từ 1.
• Cận trên v <= n - k + i đảm bảo mọi nhánh đều đi tới được một tổ hợp: không có nhánh cụt, số lá của cây đúng bằng $C_n^k$.

Không gian$O(k)$

Thời gian$O(k \cdot C_n^k)$

Kết quả chạy thật: C++: đúng 100/100 test, test chậm nhất chạy 0.077 giây. Bản Python: Python: đúng 100/100 test, test chậm nhất chạy 0.227 giây.

Ghi chú của mình: cả 2 cách đều đạt 100/100 test trên bộ test của CLUE OJ (C++ và Python). Cách 2 là khuôn mẫu sinh tổ hợp chuẩn, các bạn nên thuộc lòng – đặc biệt là cận n - k + i.

Rất vui khi anh em nào đã đọc đến những dòng cuối cùng này. Anh em đọc chắc cũng mỏi mắt luôn chứ 😅 vậy anh em nghĩ người viết ra hết đống ở trên còn thế nào nữa 🤪. Vậy nên đừng tiếc gì cho mình một lời bình luận hoặc chia sẻ bài viết để động viên mình nè. Chúc anh em học tốt và gặt hái nhiều thành công 😇