# LƯU Ý
### CHỈ NÊN ĐỌC KHI THẬT SỰ KHÔNG BIẾT LÀM HOẶC MUỐN THAM KHẢO CÁCH LÀM KHÁC
## SOLUTION
### Để làm được bài này, ta sử dụng cấu trúc gần giống với bài liệt kê hoán vị của xâu nhị phân của độ dài là n
- Trước hết, ta sẽ quay lui với với các số từ 1 đến n. Nhưng đặc biệt ở bài này, ta sẽ sử dụng thêm 1 mảng đánh dấu nữa,
mảng này sẽ được dùng để đánh dấu các phần tử ta đã duyệt rồi để tránh trùng gây ra các hoán vị lặp.
- <sub>Vd: khi không dùng mảng đánh dấu, ta sẽ tạo ra các hoán vị như: 122 hay 131,...<sub>
**Mã giả tham khảo, dựa trên ý tưởng vừa nêu:**
function backtrack(i):
if i == n:
print a[1..n] // In ket qua
return
for idx from 1 to n:
if idx is not used:
a[i] = idx
mark idx as used
backtrack(i + 1)
unmark idx as used // Backtrack, de nhung lan tiep theo co the su dung
Nên tự code dựa trên mã giả và chạy thử, khi có ẩn khuất hay vấn đề gì thì có thể đến phần code C++ ở dưới:
#include <bits/stdc++.h>
using namespace std;
int n, used[100], a[100];
void Try(int i) {
for (int j = 1; j <= n; ++j) {
if (!used[j]) {
a[i] = j;
used[j] = 1;
if (i == n) {
for (int idx = 1; idx <= n; ++idx)
cout << a[idx] << (idx == n ? '\n' : ' ');
} else
Try(i + 1);
used[j] = 0;
}
}
}
int main() {
cin >> n;
memset(used, 0, sizeof(used)); // Danh dau la moi phan tu deu chua duoc su dung
Try(1);
return 0;
}
### Giải thích phần quay lui
Ta có cây quay lui với n = 3 như sau:
"1" "2" "3"
/ \ / \ / \
"12" "13" "21" "23" "31" "32"
/ \ / \ / \
"123" "132" "213" "231" "312" "321"
Như thế ta sẽ có 3! hoán vị là: 123, 132, 213, 231, 312 và 321.
## Vậy tổng kết lại, bài này giúp ta cách để áp dụng thêm mảng đánh dấu từ đó hiểu rõ hơn về quay lui(backtracking) từ đó xây dựng nền tảng để có thể giải được các bài phức tạp hơn. Cảm ơn mọi người đã đọc!! <3
trmth1904
Created at
0 likes