Backtracking

Cây quyết định

Bài toán nhỏ: in mọi xâu nhị phân độ dài $n$ không có hai chữ số 1 đứng kề nhau. Duyệt cả $2^n$ xâu rồi lọc thì đúng nhưng phí: với $n = 30$ có $10^9$ xâu, xâu hợp lệ chỉ khoảng $0{,}2\%$.

Với $n = 3$ ta viết ba vòng for lồng nhau, mỗi vòng chọn một chữ số. Nhưng $n$ đọc từ input thì không viết được “$n$ vòng for”. Đệ quy chính là vòng lặp lồng nhau với độ sâu tùy ý: hàm go(pos) nhận tiền tố đã chốt gồm các vị trí trước pos, thử từng chữ số cho vị trí pos, và với mỗi chữ số dùng được thì gọi go(pos + 1). Mỗi lời gọi là một nút của cây quyết định; khi một nhánh duyệt xong, hàm trả về nút cha (“quay lui”) và nút cha thử lựa chọn kế tiếp. Khác với vét cạn ở một dòng continue: chữ số vừa thử làm hai số 1 kề nhau thì không gọi đệ quy, cả cây con phía dưới biến mất.

void go(ll pos) {
    if (pos > n) {
        cout << s + 1 << '\n';
        return;
    }
    for (char c = '0'; c <= '1'; c++) {
        if (c == '1' && s[pos - 1] == '1') continue;
        s[pos] = c;
        go(pos + 1);
    }
}

Ở đây s là mảng ký tự toàn cục dùng từ s[1]: s[0] để trống làm lính canh nên vị trí đầu không phải xét riêng, và s[n + 1] có sẵn ký tự kết thúc xâu. Không có dòng hoàn tác: lần thử sau ghi đè s[pos], và go(pos + 1) chỉ đọc các vị trí trước nó.

Phép cắt đúng vì điều kiện của đề là bền: tiền tố đã chứa 11 thì mọi xâu bắt đầu bằng nó đều chứa 11. Chỉ với điều kiện bền ta mới cắt mà không mất nghiệm. Điều kiện như “tổng cuối cùng bằng $S$” thì chưa thể kết luận giữa chừng, và muốn cắt theo nó phải có thêm lập luận.

Tập con

Một họ bài lớn hỏi về tập con. Mỗi phần tử có hai khả năng, chọn hoặc bỏ, nên cây là cây nhị phân đầy đủ độ sâu $n$: $2^n$ lá và $2^{n+1} - 1$ nút. Quay lui đi cùng cây, mang theo trạng thái như tổng đang có hay danh sách đã chọn:

void go(ll i, ll sum) {
    if (i > n) {
        if (sum == s) ans++;
        return;
    }
    go(i + 1, sum);
    go(i + 1, sum + a[i]);
}

Có hai kiểu trạng thái, và đây là chỗ nhiều người vấp. sum truyền theo giá trị: mỗi lời gọi có bản sao riêng, hàm trả về thì bản của nút cha vẫn nguyên, không cần hoàn tác. Một biến chung như danh sách phần tử đã chọn thì khác: nhánh chọn sửa nó trước khi đệ quy, nên phải trả lại ngay sau đó. Quy tắc dùng cho cả bài: bất cứ gì sửa trước lời gọi đệ quy phải được khôi phục ngay sau nó, như push_back đi với pop_back, đánh dấu đi với bỏ đánh dấu. Khung chung:

go(trạng thái):
    nếu đã đủ nghiệm: ghi nhận, thoát
    với mỗi lựa chọn hợp lệ:
        áp dụng lựa chọn
        go(trạng thái mới)
        hoàn tác lựa chọn

Nếu mọi $a_i$ dương thì tổng chỉ tăng, nên thêm if (sum > s) return; là cắt đúng. Với số âm, dòng đó làm mất nghiệm. Cách đúng cho số bất kỳ là đóng khung kết quả: tổng cuối nằm trong đoạn từ sum + neg[i] đến sum + pos[i], với pos[i], neg[i] là tổng các số dương, tổng các số âm từ $i$ trở đi; mục tiêu nằm ngoài đoạn thì không còn hy vọng.

Ví dụĐếm Tập Con Theo Tổng

Đề. Dãy $N \le 20$ số, $|a_i| \le 10^5$, và số $S$. Đếm số tập con không rỗng (theo vị trí) có tổng đúng bằng $S$.

Lời giải. Cây chọn hoặc bỏ, $2^{20} \approx 10^6$ lá. Có số âm nên không cắt kiểu “tổng đã vượt”. Chỗ dễ sai là tập rỗng: khi $S = 0$, lá “bỏ hết” có tổng 0 nhưng không được tính. Mang thêm số phần tử đã chọn, hoặc trừ 1 ở cuối khi $S = 0$.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, s, a[25], ans;

void go(ll i, ll sum, ll cnt) {
    if (i > n) {
        if (sum == s && cnt > 0) ans++;
        return;
    }
    go(i + 1, sum, cnt);
    go(i + 1, sum + a[i], cnt + 1);
}

signed main() {
    cin >> n >> s;
    for (ll i = 1; i <= n; i++) cin >> a[i];
    go(1, 0, 0);
    cout << ans << '\n';
}

ChạyInput3 0
-1 0 1

Output3

Hoán vị

Khi thứ tự quan trọng và mỗi giá trị chỉ dùng một lần, mỗi vị trí chọn một giá trị chưa dùng; mảng used cho biết giá trị nào đã dùng. Đánh dấu trước lời gọi, bỏ đánh dấu sau lời gọi: hai dòng hoàn tác là hình ảnh phản chiếu của hai dòng áp dụng. Thiếu một trong hai là lỗi quay lui hay gặp nhất, và nó không báo lỗi gì: chương trình vẫn chạy, chỉ in thiếu.

Số nút của cây hoán vị tính được ngay: tầng 1 có $n$ nút, tầng 2 có $n(n-1)$ nút, tầng 3 có $n(n-1)(n-2)$ nút, và tầng cuối có $n!$ lá. Cộng mọi tầng lại được khoảng $2{,}7 \cdot n!$ nút, chỉ gấp khoảng $2{,}7$ lần số lá. Với $n = 10$ có $3{,}6$ triệu lá và $9{,}9$ triệu nút, mỗi nút thử $n$ giá trị: khoảng $10^8$ phép, trần thực tế của việc duyệt hoán vị. Nếu chỉ cần mọi hoán vị mà không có điều kiện để cắt, next_permutation (bài 00) gọn hơn; quay lui đáng dùng khi có ràng buộc cắt được giữa chừng.

Con số $10^8$ chỉ đúng khi mỗi nút làm rất ít việc. Viết trạng thái thành vector truyền theo giá trị thì mỗi nút chép lại cả dãy và xin bộ nhớ mới:

Cùng 9,9 triệu nút, bản chép vector chậm hơn khoảng 35 lần. Trạng thái nào lớn hơn vài số nguyên thì để ở mảng toàn cục rồi hoàn tác.

Ví dụDãy Chọn Không Lặp

Đề. Liệt kê mọi dãy $(x_1, \dots, x_m)$ với $x_i \in [1, n]$ đôi một khác nhau, theo thứ tự từ điển. $m \le n \le 8$.

Lời giải. Khung hoán vị dừng ở độ sâu $m$. Thử $v$ tăng dần cho đúng thứ tự từ điển. Có $\frac{n!}{(n-m)!} \le 40\,320$ dãy.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, m, x[10];
bool used[10];

void go(ll i) {
    if (i > m) {
        for (ll j = 1; j <= m; j++) cout << x[j] << " \n"[j == m];
        return;
    }
    for (ll v = 1; v <= n; v++) {
        if (used[v]) continue;
        used[v] = true;
        x[i] = v;
        go(i + 1);
        used[v] = false;
    }
}

signed main() {
    cin >> n >> m;
    go(1);
}

ChạyInput3 2

Output1 2
1 3
2 1
2 3
3 1
3 2

Tổ hợp

In mọi cách chọn $k$ số từ $1..n$, coi $\{1, 3\}$ và $\{3, 1\}$ là một. Dùng khung hoán vị thì mỗi tập xuất hiện $k!$ lần. Cách sửa là ép mỗi tập chỉ có một cách viết: theo thứ tự tăng dần. Phần tử đặt sau phải lớn hơn phần tử đặt trước, nên vị trí $i$ chỉ thử các giá trị lớn hơn $x_{i-1}$.

Cắt thêm một nhát: chọn $v$ ở vị trí $i$ thì sau nó còn phải đủ $k - i$ giá trị lớn hơn, tức $v \le n - (k - i)$. Thử $v$ lớn hơn chắc chắn không đủ chỗ. Gán $x_0 = 0$ để vị trí đầu bắt đầu từ 1:

void go(ll i) {
    if (i > k) {
        for (ll j = 1; j <= k; j++) cout << x[j] << " \n"[j == k];
        return;
    }
    for (ll v = x[i - 1] + 1; v <= n - (k - i); v++) {
        x[i] = v;
        go(i + 1);
    }
}

Sau khi cắt, mọi nút đều nằm trên đường tới một lá; số lá đúng bằng số cách chọn $k$ số từ $n$ số, ký hiệu $\binom{n}{k}$ (đọc là “tổ hợp chập $k$ của $n$”, bằng $\frac{n!}{k!\,(n-k)!}$). Thử $v$ tăng dần thì các tập được in theo thứ tự từ điển.

Tám hậu

Tám hậu: đặt tám hậu lên bàn $8 \times 8$ sao cho không hai quân cùng hàng, cùng cột hay cùng đường chéo. Hãy thu hẹp không gian từng bước. Mỗi hàng đúng một hậu: còn $8^8 \approx 1{,}7 \cdot 10^7$ cách. Khác cột: $8! = 40\,320$. Quay lui đi thêm một bước: kiểm đường chéo ngay khi vừa đặt từng hậu, và chỉ còn 2057 nút.

Đặt hậu từng hàng từ trên xuống. Hai ô $(r, c)$ và $(r', c')$ cùng đường chéo khi $r - c = r' - c'$ hoặc $r + c = r' + c'$, nên ba mảng đánh dấu trả lời “ô này có bị tấn công không” trong $O(1)$: col[c], d1[r + c] và d2[r - c + n] (cộng $n$ để chỉ số không âm).

void place(ll r) {
    if (r > n) {
        ans++;
        return;
    }
    for (ll c = 1; c <= n; c++) {
        if (col[c] || d1[r + c] || d2[r - c + n]) continue;
        col[c] = d1[r + c] = d2[r - c + n] = true;
        place(r + 1);
        col[c] = d1[r + c] = d2[r - c + n] = false;
    }
}

Ba nguyên tắc nằm sau chương trình. Chỉ kiểm cái mới: các hậu cũ đã không tấn công nhau, chỉ cần kiểm hậu mới, và mảng đánh dấu làm việc đó trong $O(1)$. Cắt càng gần gốc càng lợi: một nhát cắt ở độ sâu nhỏ xóa cả cây con rất lớn. Chỉ cắt khi chứng minh được nhánh không thể hoàn thành: hàm cắt được phép bỏ sót nhánh vô vọng, nhưng không được kết luận nhầm một nhánh còn có nghiệm.

Cây bị cắt thì không có công thức đẹp cho số nút, và cách đáng tin nhất là đếm: thêm nodes++ ở đầu hàm, chạy với $n$ nhỏ rồi nhìn tốc độ tăng. Tám hậu có $2057$ nút ($n = 8$), $35\,539$ ($n = 10$), $856\,189$ ($n = 12$), $27\,358\,553$ ($n = 14$): mỗi lần $n$ tăng 1, số nút nhân lên 4 tới 6 lần. Khi không chạy thử được, có thể ước lượng bằng cách thả ngẫu nhiên từ gốc xuống (cách của Knuth): ở mỗi nút đếm số con $b$ rồi chọn một con ngẫu nhiên, ước lượng là $1 + b_0 + b_0 b_1 + \dots$ dọc đường đi, lấy trung bình nhiều lần.

Ví dụTám Hậu Trên Ô Trống

Đề. Bàn $8 \times 8$, ô . được đặt hậu, ô * bị cấm. Đếm số cách đặt đúng tám hậu vào ô được phép, không hai hậu tấn công nhau. Ô cấm chỉ ngăn đặt hậu tại chính nó, không chặn đường tấn công.

Lời giải. Đúng như trên, thêm một phép lọc: ô $(r, c)$ phải là .. Ô cấm chỉ làm cây ít nút hơn, không quá 2057 nút. Chỗ dễ sai là coi ô * như chướng ngại chặn đường tấn công; đề nói rõ nó không chặn.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll ans;
string b[10];
bool col[10], d1[20], d2[20];

void place(ll r) {
    if (r == 8) {
        ans++;
        return;
    }
    for (ll c = 0; c < 8; c++) {
        if (b[r][c] == '*' || col[c] || d1[r + c] || d2[r - c + 8]) continue;
        col[c] = d1[r + c] = d2[r - c + 8] = true;
        place(r + 1);
        col[c] = d1[r + c] = d2[r - c + 8] = false;
    }
}

signed main() {
    for (ll r = 0; r < 8; r++) cin >> b[r];
    place(0);
    cout << ans << '\n';
}

ChạyInput........
..*.....
........
....*...
........
......*.
.*......
........

Output50

Mỗi nghiệm một lần

Khi đề yêu cầu đếm, mỗi nghiệm phải ứng với đúng một đường từ gốc tới lá: đủ (ít nhất một đường) và không thừa (không quá một đường). Thừa thì đếm trùng, thường gấp lên một hệ số kiểu $k!$. Có bốn cách chuẩn.

Thứ tự tăng cho tập, đã gặp ở mục tổ hợp.

Phần tử lặp. Hoán vị các chữ của aab: đánh dấu theo vị trí thì hai chữ a bị coi là khác nhau và aab sinh ra hai lần. Cách sửa là đếm tần suất cnt[ch] và thử từng chữ cái khác nhau còn lại thay vì từng vị trí. Một xâu đích xác định duy nhất chữ cái ở mỗi vị trí, nên có đúng một đường; số lá là $\frac{n!}{c_1!\,c_2!\cdots}$.

Đối xứng. Chia $N$ người thành hai đội bằng nhau không tên: duyệt mọi tập $N/2$ người thì mỗi cách chia bị tính hai lần. Cố định người số 1 vào đội đầu thì chỉ còn một nửa. Xếp số quanh vòng tròn mà các phép quay coi là một: cố định số 1 ở đầu, còn $(n-1)!$.

Ô trống đầu tiên. Đếm cách lát bảng bằng domino $1 \times 2$: thay vì “đặt domino ở đâu cũng được”, luôn xét ô trống đầu tiên $p$ theo thứ tự hàng rồi cột. Mọi ô trước $p$ đã phủ, nên domino phủ $p$ chỉ có thể nằm ngang (sang phải) hoặc đứng (xuống dưới). Cách lát nào cũng là một dãy domino sắp theo ô đầu tăng dần, dãy đó duy nhất.

Ví dụHoán Vị Phân Biệt

Đề. Xâu $s$ dài không quá 8 chữ cái thường. In số xâu khác nhau tạo được bằng cách xếp lại các ký tự của $s$, rồi in các xâu đó theo thứ tự từ điển.

Lời giải. Đếm tần suất từng chữ cái. Ở mỗi vị trí thử từng chữ cái còn số lượng, theo thứ tự a tới z, nên các xâu sinh ra không trùng và đúng thứ tự từ điển. Đề đòi in số lượng trước, nên gom các xâu vào một danh sách rồi in. Có không quá $8! = 40\,320$ xâu.

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll n, cnt[26];
string s, cur;
vector<string> res;

void go() {
    if ((ll)cur.size() == n) {
        res.push_back(cur);
        return;
    }
    for (ll ch = 0; ch < 26; ch++) {
        if (cnt[ch] == 0) continue;
        cnt[ch]--;
        cur.push_back('a' + ch);
        go();
        cur.pop_back();
        cnt[ch]++;
    }
}

signed main() {
    cin >> s;
    n = s.size();
    for (char c : s) cnt[c - 'a']++;
    go();
    cout << res.size() << '\n';
    for (string x : res) cout << x << '\n';
}

ChạyInputaab

Output3
aab
aba
baa

Dừng sớm, cắt theo cận

Không phải bài nào cũng cần mọi nghiệm.

Chỉ cần một nghiệm, hoặc có/không. Cho hàm trả về bool: true nghĩa là đã tìm thấy. Nút nào thấy một con trả true thì trả true ngay, và không hoàn tác, vì trạng thái lúc đó chính là nghiệm cần giữ để in. Thử lựa chọn theo thứ tự tăng thì nghiệm đầu tiên tìm được là nghiệm nhỏ nhất theo thứ tự từ điển; với tám hậu nó ra sau 114 nút trong khi cây đầy đủ có 2057 nút.

Bài tối ưu. Giữ best là giá trị tốt nhất đã thấy. Với bài tìm cực tiểu mà chi phí chỉ tăng khi đi sâu, nhánh nào đã có cost >= best thì khỏi đi tiếp. Tổng quát hơn, nếu có một cận dưới lb của chi phí phần còn lại (ước lượng lạc quan, không bao giờ lớn hơn chi phí thật) thì cắt khi cost + lb >= best: mọi lá dưới nút này có chi phí ít nhất cost + lb. Kỹ thuật này gọi là nhánh và cận (branch and bound). lb thổi phồng sẽ cắt nhầm nhánh chứa nghiệm tối ưu; dấu >= loại cả phương án bằng best, ổn khi chỉ cần giá trị tối ưu nhưng sai khi phải đếm số nghiệm tối ưu.

Thứ tự thử các con. Đổi thứ tự thử không đổi tập nghiệm, chỉ đổi thời gian. Thử trước lựa chọn hứa hẹn nhất giúp best tốt lên sớm, nên các nhánh sau bị cắt nhiều hơn.

Khi nào nên bỏ quay lui? Khi các nhánh khác nhau dẫn tới cùng một trạng thái còn lại (tập ô đã phủ, tập số đã dùng): ghi nhớ kết quả, tức quy hoạch động (bài 12, 15). Khi $n$ cỡ 30 tới 40 với bài chọn tập con: chia đôi rồi ghép (bài 10).

Ví dụPhủ Các Ô Được Chọn

Đề. Bảng $10 \times 10$ gồm ô 0 và 1. Có năm tờ giấy vuông cho mỗi cỡ $1 \times 1, \dots, 5 \times 5$. Mỗi tờ nằm trọn trong bảng, chỉ phủ ô 1, không chồng nhau. Phủ toàn bộ ô 1 bằng ít tờ nhất, hoặc in $-1$.

Lời giải. Luôn xét ô 1 chưa phủ đầu tiên $p$ theo thứ tự hàng rồi cột. Tờ phủ $p$ phải có góc trên trái đúng tại $p$: góc trên trái của một hình vuông chứa $p$ đứng trước hoặc trùng $p$, mà mọi ô trước $p$ là ô 0 hoặc đã phủ. Vậy ở mỗi nút chỉ cần thử cỡ tờ, không cần thử vị trí, và mỗi cách phủ được sinh đúng một lần. Cắt khi số tờ đã dùng >= best, thử tờ to trước để best giảm nhanh. Ở bảng toàn số 1, không cắt thì cây có 424 304 nút, có cắt thì chỉ 378 nút.

Bước 1: bảng đánh dấu. a[r][c] = 1 nghĩa là ô $(r, c)$ là ô 1 chưa phủ. Đọc bảng xong thì mọi ô 1 đều chưa phủ. paper[s] đếm số tờ cỡ $s$ còn lại, best = 26 là giá trị “chưa có nghiệm”, vì tổng số tờ chỉ là 25.

for (ll r = 0; r < 10; r++)
    for (ll c = 0; c < 10; c++) cin >> a[r][c];

Bước 2: tờ có đặt được không. Tờ cạnh $s$, góc trên trái $(r, c)$ chiếm các hàng $r..r + s - 1$ và các cột $c..c + s - 1$. Tờ đặt được khi nằm trong bảng và mọi ô nó che đều là ô 1 chưa phủ.

bool fits(ll r, ll c, ll s) {
    if (r + s > 10 || c + s > 10) return false;
    for (ll i = r; i < r + s; i++)
        for (ll j = c; j < c + s; j++)
            if (!a[i][j]) return false;
    return true;
}

Bước 3: đặt và nhấc tờ. Đặt tờ là gán 0 cho mọi ô nó che, nhấc tờ là gán lại 1. Một hàm nhận giá trị cần gán làm được cả hai việc.

void put(ll r, ll c, ll s, ll v) {
    for (ll i = r; i < r + s; i++)
        for (ll j = c; j < c + s; j++) a[i][j] = v;
}

Bước 4: quay lui. dfs(used) cắt ngay nếu đã dùng không ít hơn best tờ. Đánh số ô từ 0 tới 99 theo hàng rồi cột, ô số $p$ nằm ở hàng $p / 10$, cột $p \bmod 10$; quét số $p$ tăng dần để tìm ô chưa phủ đầu tiên. Không còn ô nào thì đã phủ xong, cập nhật best. Còn lại, thử cỡ $s$ từ 5 xuống 1, mỗi cỡ còn giấy và đặt được thì áp dụng (giảm paper, đặt tờ), gọi tiếp, rồi hoàn tác theo thứ tự ngược lại.

void dfs(ll used) {
    if (used >= best) return;
    ll p = 0;
    while (p < 100 && !a[p / 10][p % 10]) p++;
    if (p == 100) {
        best = used;
        return;
    }
    ll r = p / 10, c = p % 10;
    for (ll s = 5; s >= 1; s--) {
        if (paper[s] == 0 || !fits(r, c, s)) continue;
        paper[s]--;
        put(r, c, s, 0);
        dfs(used + 1);
        put(r, c, s, 1);
        paper[s]++;
    }
}

Ghép lại, main đọc bảng, gọi dfs(0) và in $-1$ nếu best vẫn là 26:

#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll a[10][10], paper[6] = {0, 5, 5, 5, 5, 5}, best = 26;

bool fits(ll r, ll c, ll s) {
    if (r + s > 10 || c + s > 10) return false;
    for (ll i = r; i < r + s; i++)
        for (ll j = c; j < c + s; j++)
            if (!a[i][j]) return false;
    return true;
}

void put(ll r, ll c, ll s, ll v) {
    for (ll i = r; i < r + s; i++)
        for (ll j = c; j < c + s; j++) a[i][j] = v;
}

void dfs(ll used) {
    if (used >= best) return;
    ll p = 0;
    while (p < 100 && !a[p / 10][p % 10]) p++;
    if (p == 100) {
        best = used;
        return;
    }
    ll r = p / 10, c = p % 10;
    for (ll s = 5; s >= 1; s--) {
        if (paper[s] == 0 || !fits(r, c, s)) continue;
        paper[s]--;
        put(r, c, s, 0);
        dfs(used + 1);
        put(r, c, s, 1);
        paper[s]++;
    }
}

signed main() {
    for (ll r = 0; r < 10; r++)
        for (ll c = 0; c < 10; c++) cin >> a[r][c];
    dfs(0);
    cout << (best == 26 ? -1 : best) << '\n';
}

ChạyInput1 1 0 0 0 0 0 0 0 0
1 1 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0

Output1

Mỗi nút quét tối đa 100 ô và thử nhiều nhất 5 cỡ, mỗi cỡ tốn tối đa 25 phép; số nút nhỏ nhờ cắt theo best và nhờ chỉ xét một ô ở mỗi nút.