Quay lui (1)
- Độ khó
- ★★★★☆ Khó
- Thời lượng
- Khoảng 120 phút
- Học trước
- Sinh kế tiếp, Hàm tự tạo và đệ quy
- Chủ đề
- quay luiđệ quy
- Trạng thái
Kiến thức cơ bản
Vì sao cần quay lui
Tuần trước, em đã sinh kế tiếp cho từng loại cấu hình: dãy nhị phân, tổ hợp, hoán vị, mỗi loại một luật riêng. Nếu đề bài lại thêm điều kiện (ví dụ “không có hai số 1 đứng cạnh nhau”) thì luật sinh kế tiếp phải nghĩ lại từ đầu. Quay lui cho em một khuôn chung để giải mọi bài kiểu này, dựa trên đệ quy mà em đã học ở tuần 7.
Hãy tưởng tượng Thỏ đi trong một khu rừng có nhiều ngã rẽ và muốn đi hết mọi con đường. Ở mỗi ngã rẽ, Thỏ chọn một nhánh, đi tiếp. Khi đi đến cuối đường (hoặc gặp ngõ cụt), Thỏ quay lui về ngã rẽ gần nhất và thử nhánh khác. Mỗi lần quay lui, Thỏ xóa dấu chân của nhánh vừa thử. Các đoạn code dưới đây dùng các hàm đệ quy và biến toàn cục.
Khuôn mẫu của quay lui
void Try(int pos) {
if (đã chọn đủ) { xử lý kết quả; return; } // 1. dừng
for (mỗi lựa chọn c) {
if (c hợp lệ) { // 2. kiểm tra
ghi lại c; // 3. thử c
Try(pos + 1); // 4. đi tiếp
hủy c; // 5. quay lui
}
}
}
Điều quan trọng nhất là bước 5. Mỗi lần thử xong một lựa chọn, ta phải trả lại mọi thứ đúng như lúc chưa thử (xóa dấu chân), để lựa chọn tiếp theo bắt đầu từ trạng thái sạch.
Mẫu 1: Liệt kê dãy nhị phân
Với n = 2, các lựa chọn tạo thành một cây. Mỗi đường đi từ gốc đến lá là một dãy. Quay lui duyệt cây này từ trái sang phải, theo thứ tự in ra 00, 01, 10, 11.
Try(0)
/ \
chọn 0 chọn 1
Try(1) Try(1)
/ \ / \
chọn 0 chọn 1 chọn 0 chọn 1
"00" "01" "10" "11"
int n;
vector<int> path; // dãy đang xây dựng
void Try(int pos) { // đang chọn phần tử thứ pos
if (pos == n) { // điều kiện dừng: đã chọn đủ n số
for (int x : path) cout << x;
cout << "\n";
return;
}
for (int c = 0; c <= 1; c++) { // thử từng cách chọn
path.push_back(c); // ghi lựa chọn
Try(pos + 1); // đi tiếp
path.pop_back(); // quay lui: hủy lựa chọn để thử cách khác
}
}
// trong main: cin >> n; Try(0);
Để ghi và hủy lựa chọn thật gọn, ta dùng một vector path: push_back để ghi, pop_back để hủy. Hai dòng ấy luôn đứng hai bên lời gọi Try(pos + 1).
Mẫu 2: Liệt kê hoán vị
Mỗi số từ 1 đến n chỉ xuất hiện đúng một lần, nên ta cần một mảng đánh dấu used[v] để nhớ số nào đã dùng. Số nào chưa dùng mới được thử. Nhớ bỏ đánh dấu khi quay lui.
int n;
vector<int> path;
bool used[20]; // used[v] = true nếu số v đã được dùng
void Try(int pos) {
if (pos == n) {
for (int x : path) cout << x << " ";
cout << "\n";
return;
}
for (int v = 1; v <= n; v++) {
if (used[v]) continue; // số v đã có trong dãy: bỏ qua
used[v] = true; // đánh dấu
path.push_back(v);
Try(pos + 1);
path.pop_back(); // quay lui
used[v] = false; // bỏ đánh dấu
}
}
Mẫu 3: Liệt kê tổ hợp
Để chọn k số tăng dần từ 1 đến n, ta thêm tham số start là số nhỏ nhất được phép chọn tiếp. Sau khi chọn số v, số tiếp theo phải bắt đầu từ v + 1, nhờ vậy mỗi tập chỉ xuất hiện một lần theo thứ tự tăng dần.
int n, k;
vector<int> path;
void Try(int start) { // start: số nhỏ nhất được phép chọn tiếp
if ((int)path.size() == k) {
for (int x : path) cout << x << " ";
cout << "\n";
return;
}
for (int v = start; v <= n; v++) {
path.push_back(v);
Try(v + 1); // số tiếp theo phải lớn hơn v
path.pop_back();
}
}
Mẫu 4: Cắt tỉa nhánh vô ích
Bài toán: có n số dương, đếm số cách chọn một số số sao cho tổng đúng bằng S. Mỗi số có hai khả năng: chọn hoặc không chọn, nên có 2^n khả năng. Nhưng khi tổng đã vượt S thì mọi lựa chọn tiếp theo đều vô ích (vì số dương chỉ làm tổng tăng thêm). Ta quay lui ngay lập tức, không đi tiếp. Việc bỏ nhánh sớm như vậy gọi là cắt tỉa.
int n, S, dem = 0;
vector<int> a; // các số đều dương
void Try(int i, long long sum) {
if (sum > S) return; // cắt tỉa: tổng đã vượt S thì bỏ cả nhánh
if (i == n) {
if (sum == S) dem++;
return;
}
Try(i + 1, sum + a[i]); // chọn phần tử i
Try(i + 1, sum); // không chọn phần tử i
}
Khi ước lượng thời gian, em đếm số cấu hình phải duyệt: 2^n với dãy nhị phân hoặc tập con, C(n, k) với tổ hợp, n! với hoán vị. Cắt tỉa tốt có thể giảm rất nhiều, nhưng em không nên dựa vào nó nếu chưa chắc chắn. Với n khoảng 20 thì 2^n vẫn ổn, còn n! chỉ ổn khi n không quá 9 hoặc 10.
Nhận dạng đề bài
| Dấu hiệu trong đề | Cách làm | Điều cần chú ý |
|---|---|---|
| Liệt kê mọi dãy, mọi cách chọn theo một thứ tự nào đó | Try(pos) thử từng lựa chọn, đi tiếp, rồi quay lui | Thứ tự duyệt for quyết định thứ tự in ra |
| Mỗi số chỉ dùng một lần (hoán vị) | Thêm mảng đánh dấu used[] | Đánh dấu trước khi gọi Try, bỏ đánh dấu sau khi gọi |
| Chọn k phần tử, thứ tự không quan trọng (tổ hợp) | Try(start), số sau lớn hơn số trước | Lần gọi tiếp theo là Try(v + 1) |
| Đếm cách thỏa điều kiện, điều kiện sai là bỏ cả nhánh | Cắt tỉa: gặp điều kiện sai thì return sớm | Cắt tỉa sớm giúp tránh duyệt vô ích |
Luyện tập
Bài 1. Cờ hiệu hai màu
Gấu Po làm cờ hiệu gồm n lá cờ nhỏ xếp thành hàng, mỗi lá chỉ có hai màu: màu a hoặc màu b. Hãy liệt kê mọi cờ hiệu khác nhau theo thứ tự bảng chữ cái. Hãy giải bằng quay lui.
| Đầu vào | Một dòng duy nhất là số nguyên n (1 ≤ n ≤ 10). | |
|---|---|---|
| Đầu ra | 2^n dòng, mỗi dòng một xâu gồm n ký tự a hoặc b, theo thứ tự từ điển. | |
| Test | Input | Output |
| 1 | 2 | aa ab ba bb |
| 2 | 3 | aaa aab aba abb baa bab bba bbb |
Bài 2. Hàng đèn không kề nhau
Hổ có n bóng đèn xếp thành hàng, mỗi bóng sáng (1) hoặc tắt (0). Để tiết kiệm điện, không có hai bóng sáng nào đứng cạnh nhau. Hãy liệt kê mọi cách bật tắt theo thứ tự từ điển.
| Đầu vào | Một dòng duy nhất là số nguyên n (1 ≤ n ≤ 12). | |
|---|---|---|
| Đầu ra | Mỗi dòng một xâu gồm n ký tự 0 hoặc 1 hợp lệ, theo thứ tự từ điển. | |
| Test | Input | Output |
| 1 | 3 | 000 001 010 100 101 |
| 2 | 4 | 0000 0001 0010 0100 0101 1000 1001 1010 |
Bài 3. Xếp hàng chụp ảnh
Thỏ muốn chụp ảnh cho n bạn đánh số từ 1 đến n đứng thành một hàng. Hãy liệt kê mọi cách xếp hàng theo thứ tự từ điển bằng quay lui.
| Đầu vào | Một dòng duy nhất là số nguyên n (1 ≤ n ≤ 7). | |
|---|---|---|
| Đầu ra | n! dòng, mỗi dòng gồm n số cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 3 | 1 2 3 1 3 2 2 1 3 2 3 1 3 1 2 3 2 1 |
| 2 | 1 | 1 |
Bài 4. Chọn đội trực nhật
Lớp có n bạn đánh số từ 1 đến n. Hãy liệt kê mọi cách chọn k bạn đi trực nhật theo thứ tự từ điển. Mỗi cách chọn viết các số tăng dần.
| Đầu vào | Một dòng gồm hai số nguyên n, k (1 ≤ k ≤ n ≤ 10). | |
|---|---|---|
| Đầu ra | Mỗi dòng một cách chọn gồm k số tăng dần cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 4 2 | 1 2 1 3 1 4 2 3 2 4 3 4 |
| 2 | 3 3 | 1 2 3 |
Bài 5. Hộp quà tổng S
Gấu Po có n món quà, món thứ i có giá a[i] (đều dương). Hỏi có bao nhiêu cách chọn một số món (có thể không chọn món nào, nhưng S > 0 nên chọn rỗng không thỏa) để tổng giá đúng bằng S? Hãy dùng quay lui và cắt tỉa khi tổng vượt S.
| Đầu vào | Dòng 1: hai số nguyên n, S (1 ≤ n ≤ 20; 1 ≤ S ≤ 109). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 108). | |
|---|---|---|
| Đầu ra | Số cách chọn. | |
| Test | Input | Output |
| 1 | 4 5 1 2 3 4 | 2 |
| 2 | 3 10 1 2 3 | 0 |
| 3 | 5 4 1 1 1 1 2 | 7 |
Bài 6. Phân tích số thành tổng
Thỏ có n viên kẹo và muốn chia thành các nhóm. Một cách chia là một dãy các số nguyên dương có tổng bằng n, viết giảm dần (không tăng). Hãy liệt kê mọi cách chia, theo thứ tự: cách có số đầu tiên lớn hơn được in trước; nếu số đầu bằng nhau thì xét tiếp số thứ hai, và cứ thế.
| Đầu vào | Một dòng duy nhất là số nguyên n (1 ≤ n ≤ 12). | |
|---|---|---|
| Đầu ra | Mỗi dòng một cách chia, các số cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 4 | 4 3 1 2 2 2 1 1 1 1 1 1 |
| 2 | 1 | 1 |
Bài 7. Mã số có tổng cho trước
Hổ muốn tạo mã số gồm n chữ số (mỗi chữ số từ 0 đến 9, chữ số 0 được đứng đầu) sao cho tổng các chữ số đúng bằng S. Hãy liệt kê mọi mã số theo thứ tự tăng dần.
| Đầu vào | Một dòng gồm hai số nguyên n, S (1 ≤ n ≤ 5; 0 ≤ S ≤ 45). | |
|---|---|---|
| Đầu ra | Mỗi dòng một mã số gồm n chữ số viết liền nhau. Nếu không có mã nào thì không in gì. | |
| Test | Input | Output |
| 1 | 2 3 | 03 12 21 30 |
| 2 | 3 1 | 001 010 100 |
Bài 8. Mật khẩu của Gấu Po
Mật khẩu của Gấu Po gồm n chữ cái, mỗi chữ cái là a, b hoặc c, và hai chữ cái đứng cạnh nhau không được giống nhau. Hãy liệt kê mọi mật khẩu có thể theo thứ tự từ điển.
| Đầu vào | Một dòng duy nhất là số nguyên n (1 ≤ n ≤ 8). | |
|---|---|---|
| Đầu ra | Mỗi dòng một mật khẩu. | |
| Test | Input | Output |
| 1 | 2 | ab ac ba bc ca cb |
| 2 | 3 | aba abc aca acb bab bac bca bcb cab cac cba cbc |
Bài 9. Túi đồ chơi
Thỏ có n món đồ chơi, món thứ i nặng w[i] gram. Thỏ muốn mang đi chơi một số món (có thể không mang món nào) sao cho tổng khối lượng không vượt quá S gram và tổng khối lượng càng lớn càng tốt. Hỏi tổng khối lượng lớn nhất là bao nhiêu?
| Đầu vào | Dòng 1: hai số nguyên n, S (1 ≤ n ≤ 20; 1 ≤ S ≤ 109). Dòng 2: n số nguyên w[i] (1 ≤ w[i] ≤ 108). | |
|---|---|---|
| Đầu ra | Tổng khối lượng lớn nhất không vượt quá S. | |
| Test | Input | Output |
| 1 | 4 10 2 3 5 7 | 10 |
| 2 | 3 4 5 6 7 | 0 |
Bài tập tự luyện
Bài 1. Dãy ngoặc đúng
Thỏ viết các dãy gồm n dấu mở ngoặc ( và n dấu đóng ngoặc ). Dãy được gọi là đúng nếu mỗi dấu đóng ghép được với một dấu mở đứng trước nó. Hãy liệt kê mọi dãy ngoặc đúng, theo thứ tự từ điển (dấu ( đứng trước dấu ) ).
| Đầu vào | Một dòng duy nhất là số nguyên n (1 ≤ n ≤ 8). | |
|---|---|---|
| Đầu ra | Mỗi dòng một dãy ngoặc đúng dài 2n ký tự. | |
| Test | Input | Output |
| 1 | 2 | (()) ()() |
| 2 | 3 | ((())) (()()) (())() ()(()) ()()() |
Bài 2. Xếp hàng không kề số
Gấu Po xếp n bạn đánh số từ 1 đến n thành một hàng. Hai bạn có số hơn kém nhau đúng 1 (ví dụ 3 và 4) không được đứng cạnh nhau. Hỏi có bao nhiêu cách xếp hàng thỏa mãn?
| Đầu vào | Một dòng duy nhất là số nguyên n (1 ≤ n ≤ 9). | |
|---|---|---|
| Đầu ra | Số cách xếp hàng. | |
| Test | Input | Output |
| 1 | 3 | 0 |
| 2 | 4 | 2 |
| 3 | 5 | 14 |
Bài 3. Tổng k số
Hổ muốn chọn k số khác nhau từ 1, 2, ..., n sao cho tổng đúng bằng S. Hãy cho biết số cách chọn và liệt kê các cách, theo thứ tự từ điển.
| Đầu vào | Một dòng gồm ba số nguyên n, k, S (1 ≤ k ≤ n ≤ 12; 1 ≤ S ≤ 100). | |
|---|---|---|
| Đầu ra | Dòng 1: số cách chọn. Sau đó mỗi dòng một cách chọn gồm k số tăng dần, cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 5 3 9 | 2 1 3 5 2 3 4 |
| 2 | 3 2 100 | 0 |
Bài 4. Chia kẹo cho các bạn
Gấu Po có m viên kẹo giống hệt nhau và muốn chia hết cho n bạn. Mỗi bạn nhận ít nhất 1 viên và nhiều nhất c viên. Hỏi có bao nhiêu cách chia? Hai cách chia khác nhau nếu có một bạn nhận số kẹo khác nhau.
| Đầu vào | Một dòng gồm ba số nguyên n, m, c (1 ≤ n ≤ 8; 1 ≤ m ≤ 40; 1 ≤ c ≤ 8). | |
|---|---|---|
| Đầu ra | Số cách chia. | |
| Test | Input | Output |
| 1 | 3 6 3 | 7 |
| 2 | 2 5 3 | 2 |
Bài 5. Tổng các số khác nhau
Thỏ muốn viết số n thành tổng của các số nguyên dương đôi một khác nhau. Hãy liệt kê mọi cách viết, mỗi cách viết các số giảm dần, theo thứ tự: cách có số đầu lớn hơn được in trước (và tiếp tục như vậy).
| Đầu vào | Một dòng duy nhất là số nguyên n (1 ≤ n ≤ 20). | |
|---|---|---|
| Đầu ra | Mỗi dòng một cách viết, các số cách nhau một dấu cách. | |
| Test | Input | Output |
| 1 | 6 | 6 5 1 4 2 3 2 1 |
| 2 | 4 | 4 3 1 |
Bài 6. Nhóm bạn quen nhau
Có n bạn đánh số từ 1 đến n. Có m cặp bạn quen nhau. Gấu Po muốn chọn đúng k bạn sao cho hai bạn bất kỳ trong nhóm đều quen nhau. Hỏi có bao nhiêu cách chọn nhóm?
| Đầu vào | Dòng 1: ba số nguyên n, m, k (1 ≤ k ≤ n ≤ 12; 0 ≤ m ≤ n(n-1)/2). m dòng sau, mỗi dòng gồm hai số nguyên u, v (1 ≤ u < v ≤ n) cho biết bạn u và bạn v quen nhau. | |
|---|---|---|
| Đầu ra | Số nhóm thỏa mãn. | |
| Test | Input | Output |
| 1 | 4 5 3 1 2 1 3 2 3 2 4 3 4 | 2 |
| 2 | 3 0 2 | 0 |
Bài 7. Tô màu dải cờ
Thỏ tô màu cho dải cờ gồm n dải liền nhau, có m màu để chọn (đánh số từ 1 đến m). Hai dải kề nhau phải có màu khác nhau. Ngoài ra, có q ràng buộc, mỗi ràng buộc cho biết dải thứ i không được tô màu c. Hỏi có bao nhiêu cách tô?
| Đầu vào | Dòng 1: ba số nguyên n, m, q (1 ≤ n ≤ 8; 1 ≤ m ≤ 4; 0 ≤ q ≤ 10). q dòng sau, mỗi dòng gồm hai số nguyên i, c (1 ≤ i ≤ n; 1 ≤ c ≤ m). | |
|---|---|---|
| Đầu ra | Số cách tô màu. | |
| Test | Input | Output |
| 1 | 3 2 0 | 2 |
| 2 | 3 3 1 2 1 | 8 |
Bài 8. Chia đôi quà
Hổ có n món quà, món thứ i có giá a[i]. Hổ muốn chia các món quà thành hai phần (mỗi món thuộc đúng một phần, có thể có phần rỗng) sao cho hiệu số giữa tổng giá hai phần là nhỏ nhất. Hãy cho biết hiệu số nhỏ nhất đó.
| Đầu vào | Dòng 1: số nguyên n (1 ≤ n ≤ 20). Dòng 2: n số nguyên a[i] (1 ≤ a[i] ≤ 106). | |
|---|---|---|
| Đầu ra | Hiệu số nhỏ nhất giữa tổng hai phần. | |
| Test | Input | Output |
| 1 | 4 1 2 3 4 | 0 |
| 2 | 3 5 5 8 | 2 |
Bài 9. Thử thách (không bắt buộc): Chuyến du lịch ngắn nhất
Gấu Po xuất phát từ thành phố 1, muốn ghé thăm mỗi thành phố trong n thành phố đúng một lần rồi quay về thành phố 1. Quãng đường từ thành phố i sang thành phố j là d[i][j] (có thể d[i][j] khác d[j][i]). Hãy tìm tổng quãng đường nhỏ nhất của một chuyến đi như vậy. (Gợi ý: dùng quay lui, và cắt tỉa khi quãng đường đã đi không nhỏ hơn đáp án tốt nhất tìm được.)
| Đầu vào | Dòng 1: số nguyên n (2 ≤ n ≤ 9). n dòng tiếp theo, mỗi dòng gồm n số nguyên d[i][j] (0 ≤ d[i][j] ≤ 1000, d[i][i] = 0). | |
|---|---|---|
| Đầu ra | Tổng quãng đường nhỏ nhất. | |
| Test | Input | Output |
| 1 | 4 0 10 15 20 10 0 35 25 15 35 0 30 20 25 30 0 | 80 |
| 2 | 2 0 5 5 0 | 10 |
-
Gợi ý chung: Khi giải bằng quay lui, luôn hỏi ba câu: (1) Khi nào dừng và xử lý kết quả? (2) Ở mỗi bước có những lựa chọn nào, lựa chọn nào hợp lệ? (3) Sau khi thử xong một lựa chọn, mình đã trả lại mọi thứ như cũ chưa (pop_back, bỏ đánh dấu used)? Hầu hết lỗi sai trong quay lui nằm ở câu hỏi thứ ba.
-
Lưu ý thêm: Thứ tự in ra phụ thuộc vào thứ tự các lựa chọn trong vòng for: muốn in theo thứ tự từ điển thì thử các lựa chọn từ nhỏ đến lớn. Hãy ước lượng số cấu hình (2^n, C(n, k), n!) trước khi viết code để chắc chắn chương trình đủ nhanh.