## Đề bài
Cho tập $S = \{1, 2, ..., n\}$ và một số nguyên $k$, hãy liệt kê tất cả các tập con độ dài $k$ của $S$, theo thứ tự từ điển.
### Input
- Một dòng gồm hai số nguyên $n, k$.
- $1 \leq k \leq n \leq 20$
### Output
- In ra tất cả các tập con độ dài $k$ của $S$, mỗi tập con trên một dòng, các phần tử cách nhau bởi dấu cách.
- Các tập con được in theo thứ tự từ điển.
---
## Hướng
- Bài toán yêu cầu liệt kê **các tổ hợp chập $k$ của $n$ phần tử**.
- Ta sẽ sử dụng kỹ thuật **đệ quy (Backtracking)** để sinh các tập con có độ dài đúng bằng $k$.
- Trong mỗi bước đệ quy:
- Nếu độ dài hiện tại bằng $k$, ta in ra tập con.
- Nếu đã xét hết phần tử mà chưa đủ $k$, ta dừng.
- Ngược lại, thử chọn hoặc không chọn phần tử hiện tại.
---
## Code Python
```python
def Cactapcon(i, tapcon):
if len(tapcon) == k:
print(*tapcon)
return
if i == len(A):
return
# Chọn A[i] và lặp lại
Cactapcon(i + 1, tapcon + [A[i]])
# Không chọn A[i] và lặp lại
Cactapcon(i + 1, tapcon)
n, k = map(int, input().split())
A = [i for i in range(1, n + 1)]
Cactapcon(0, [])
ThanhDungxX
Created at
1 likes