Thắc mắc về Backtrack

[wzwowzw (Minh)]

#include <stdio.h>

int n;
bool used[123];
int a[123];

void show(){
    int i;
    for (i=1; i<=n; i++)
    printf("%d ", a[i]);
    printf("\n");
}

void back(int pos){
    int i;
    if (pos==n+1) { show(); return ; }
    for (i=1; i<=n; i++)
    if (not used[i]){
        a[pos]=i;
        used[i]=true;
        back(pos+1);
        used[i]=false;
    }
}

main(){
    scanf("%d", &n);
    back(1);
}

Mình đang bắt đầu tìm hiểu về Backtrack nên chưa hiểu, mọi người giải thích về cách hoạt động của dòng code trên giúp mình>

[nxphuc (Nguyễn Xuân Phúc)]

Thuật toán liệt kê hoán vị thì phải!
hàm đệ quy (back) sẽ thực hiện việc chọn lần lượt các giá trị của hoán vị.
Ở mỗi pos, sẽ tìm trong N số cần hoán vị số nào chưa được chọn, thử nó sẽ là phần tử thứ pos trong hoán vị mình đang xét. Khi chọn được rồi, đánh dấu là mình đã dùng nó (used[i]), cho nó là phần tử thứ pos trong hoán vị, và gọi hàm back(pos+1) để tiếp tục chọn phần tử tiếp theo cho hoán vị. Cứ như thế cho đến pos = n+1 thì tức là ta đã chọn được N phần tử cho hoán vị thì xuất ra.
Khi hàm back gọi xong đệ quy, quay ngược lại, thì lúc này ta không dùng giá trị i hiện tại làm phần tử a[pos] nữa mà tiếp tục thử giá trị khác -> i lúc này ta không dùng nữa -> giải phóng nó -> gán used[i] = false. Để lát nữa lặp hoán vị có thể dùng nó chứ không bị chiếm dụng luôn.

[nxphuc (Nguyễn Xuân Phúc)]

Ví dụ N = 3:

---

back(1):
used[] = {0, 0, 0}
a[] = {}
duyệt i = 1, chưa dùng -> used[1] = 1, a[1] = 1, gọi back(2)

---

back(2)
used[] = {1, 0, 0}
a[] = {1,}
duyệt i = 1, dùng rồi. Tăng i = 2, chưa dùng -> used[2] = 1, a[2] = 2, gọi back(3)

---

back(3)
used[] = {1, 1, 0}
a[] = {1, 2}
duyệt i = 1, dùng rồi; tăng i = 2, dùng rồi; tăng i = 3 chưa dùng -> used[3] = 1, a[3] = 3, gọi back(4)

---

back(4)
used[] = {1, 1, 1}
a[] = {1, 2, 3}
4 = n+1 -> show, dc hoán vị 1 2 3, trở về back(3)

---

back(3) - quay về
dùng 3 rồi, giờ giải phóng 3, used[3] = 0. Tăng i = 4, vượt quá N, thoát vòng lặp, hết hàm, trở về back(2)

---

back(2) - quay về
used[] = {1, 1, 0}
a[] = {1, 2}
dùng 2 rồi, giờ giải phóng 2, used[2] = 0, tăng i = 3, 3 chưa dùng -> thử dùng 3, used[3] = 1, a[2] = 3, gọi back(3)

---

back(3) - lần 2
used[] = {1, 0, 1}
a[] = {1, 3}
duyệt i = 1, dùng rồi; tăng i = 2, chưa dùng, dùng 2 -> used[2] = 1, a[3] = 2, gọi back(4)

---

back(4) - lần 2
used[] = {1, 1, 1}
a[] = {1, 3, 2}
4 = N+1 -> show hoán vị, ta được 1 hoán vị mới là 1 3 2.
Trở về back(3)

---

Cứ tương tự như vậy cho đến hết