Vét cạn và Quay lui từ trực giác đến kỹ thuật ICPC

Vét cạn là biến câu “thử hết mọi cách” thành một quy trình không bỏ sót, kiểm tra đúng và chạy đủ nhanh. Điều cần học nhất là cách chọn thứ để thử, đếm số lần phải thử và giảm công việc trong mỗi lần thử.

Bạn có thể dùng chương này theo hai lượt: lượt đầu học phần 1–2 và các mẫu 3.1–3.6; lượt sau học các mẫu còn lại cùng phần 4. Mục tiêu thực hành là tự thiết kế được phép duyệt, chứng minh nó đúng và giải thích được vì sao nó qua giới hạn.

Chuyên đề bao gồm cả quay lui, với các mẫu xây cấu hình từng bước, hoàn tác trạng thái, loại lựa chọn sai sớm, nhánh cận và duyệt đường đi. Lộ trình chính ở phần 5 gồm đầy đủ 15 bài của MarisaOJ module 9 — Backtracking, đã đối chiếu trực tiếp từng đề. Các bài Codeforces, CSES và YouKn0wWho được giữ lại để luyện thêm.

Phần 1 — Trực giác và phân tích cơ bản

1.1. Hình dung như thử chìa khóa

Bạn có một hộp khóa và 100 chìa. Bạn không biết chìa nào mở được hộp, nên thử từng chiếc. Để chắc chắn tìm được chìa phù hợp nếu nó tồn tại, bạn cần:

1. Có đủ các chìa cần thử.

2. Thử đúng cách: chìa không mở được thì không nhận nhầm là đúng.

3. Có một thứ tự để không bỏ quên chiếc nào.

Đó là ý tưởng của vét cạn. Trong lập trình, một “chiếc chìa” có thể là một cặp chỉ số, một đoạn mảng, một tập con, một cách sắp xếp hoặc cả một đường đi.

Ví dụ: có ba món đồ nặng $2,3,5$. Muốn chọn một số món có tổng khối lượng $5$, hãy thử mọi cách lấy hoặc bỏ từng món. Hai cách đúng là lấy món $5$, hoặc lấy hai món $2$ và $3$.

Viết bằng toán: gọi $\Omega$ là tập tất cả ứng viên, $P(x)$ là điều kiện đúng. Bài toán tối ưu có dạng

Vét cạn duyệt các ứng viên, kiểm tra $P(x)$ rồi cập nhật đáp án. Nếu không có ứng viên hợp lệ, phải báo không có lời giải theo yêu cầu đề.

1.2. Đề hỏi gì sẽ quyết định cách xử lý

Ví dụ, tìm được một tập con có tổng $S$ chưa cho phép dừng nếu đề yêu cầu đếm mọi tập con.

1.3. Phân biệt các khái niệm dễ lẫn

Đệ quy có thể viết thuật toán $O(N)$ hoặc thuật toán tăng theo cấp số nhân. Vét cạn cũng có thể chỉ là hai vòng lặp $O(N^2)$; nó không nhất thiết là $2^N$ hay $N!$.

1.4. Đọc constraints bằng cách đếm lựa chọn

Đừng chỉ nhìn $N$. Hãy hỏi: “Một lời giải cần bao nhiêu quyết định độc lập, và mỗi quyết định có mấy cách?”

Một vài con số nên nhớ:

Các dấu hiệu để bắt đầu suy nghĩ, không phải lời bảo đảm qua time limit:

Ví dụ, chuỗi dài $10^5$ nhưng chỉ có 15 dấu ?, mỗi dấu thay bằng 0 hoặc 1, chỉ có $2^{15}$ cách điền. Tuy nhiên, nếu mỗi cách lại quét cả chuỗi thì vẫn rất tốn: phải tính cả chi phí kiểm tra.

1.5. Công thức thời gian quan trọng nhất

Nếu chi phí không đều, công thức chính xác hơn là

Ví dụ tập con:

• Có $2^N$ tập con. Mỗi lần quét $N$ phần tử để tính tổng: $O(N2^N)$.

• DFS mang theo tổng hiện tại, mỗi cạnh chỉ cộng thêm một số: $O(2^N)$ nếu các việc còn lại là $O(1)$.

• In toàn bộ tập con: tổng lượng phần tử phải in là $N2^{N-1}$ với $N\ge1$, nên riêng output đã tốn $\Theta(N2^N)$.

Cây lựa chọn nhị phân đầy đủ có $2^N$ lá nhưng có

nút. Vì vậy đệ quy xét mọi tập con và xử lý mỗi nút trong $O(1)$ vẫn là $O(2^N)$.

Với nhiều test, tính tổng công việc:

chứ không chỉ nhìn test lớn nhất. Không có quy tắc đáng tin tuyệt đối kiểu “$10^8$ phép toán luôn chạy trong một giây”; phép chia, cấp phát, hash, truy cập bộ nhớ và xuất dữ liệu có giá rất khác nhau.

1.6. Bộ nhớ và tính đúng đắn

Một người đi khám phá cây chỉ cần nhớ con đường đang đi, không cần giữ tất cả con đường từng đi qua.

• DFS sâu tối đa $N$: stack thường $O(N)$.

• Bitmask xử lý từng tập con rồi bỏ: bộ nhớ phụ $O(1)$.

• Lưu tổng cho mọi mask: $O(2^N)$.

• Lưu mọi cấu hình dài $N$: có thể tới $O(N2^N)$ hoặc $O(NN!)$.

• Meet-in-the-middle: thường $O(2^{\lceil N/2\rceil})$.

Ở đây “bộ nhớ phụ” không tính mảng đầu vào, trừ khi có nói khác.

Để chứng minh một phép vét cạn đúng, viết được ba câu:

1. Không bỏ sót: mọi lời giải hợp lệ tương ứng với ít nhất một cấu hình được duyệt.

2. Không nhận nhầm: cấu hình chỉ được chấp nhận khi thỏa đúng điều kiện đề.

3. Không đếm sai: nếu đếm/liệt kê, mỗi lời giải được tính đúng số lần yêu cầu.

Với bài tối ưu, bổ sung: mọi ứng viên có thể cải thiện đáp án đều đã được xét hoặc đã bị loại bằng một lập luận đúng.

Phần 2 — Kỹ năng nháp và tìm hướng tiếp cận

2.1. Vẽ gì đầu tiên?

Hãy vẽ một lời giải trông như thế nào trước khi vẽ thuật toán.

Đây là bước chống một lỗi phổ biến: viết đệ quy rất nhanh nhưng đang sinh sai loại đối tượng.

2.2. Quy trình nháp bảy bước

Bước 1 — Viết một câu mô tả ứng viên.

Ví dụ: “Một ứng viên là dãy $x_0,x_1,\ldots,x_{N-1}$, trong đó $x_i=1$ nếu lấy món $i$, và bằng $0$ nếu bỏ.”

Bước 2 — Ghi miền lựa chọn và điều kiện đúng.

Hỏi thêm: có được chọn rỗng không, các phần tử bằng nhau có phải những món khác nhau không, thứ tự có quan trọng không?

Bước 3 — Tự liệt kê một input nhỏ.

Với $a=[2,3,5]$ và $S=5$:

Hàng $(x_0,x_1,x_2)$ ở đây là thứ tự quyết định, không phải quy ước viết chữ số nhị phân từ bit cao xuống bit thấp.

Bước 4 — Vẽ hai tầng của cây quyết định.

Đặt trạng thái là $(i,s)$: đã quyết định xong các món trước $i$, tổng đang có là $s$.

flowchart TD
    A["i = 0, s = 0"] -->|Bỏ 2| B["i = 1, s = 0"]
    A -->|Lấy 2| C["i = 1, s = 2"]
    B -->|Bỏ 3| D["i = 2, s = 0"]
    B -->|Lấy 3| E["i = 2, s = 3"]
    C -->|Bỏ 3| F["i = 2, s = 2"]
    C -->|Lấy 3| G["i = 2, s = 5"]

Mỗi nút ở tầng cuối hình vẫn còn phải quyết định món $5$. Không cần vẽ cả cây lớn; hai hoặc ba tầng thường đủ để nhìn ra cách gọi tiếp.

Bước 5 — Viết trạng thái chuyển đổi bằng lời rồi bằng toán.

• Bỏ món $i$: sang $(i+1,s)$.

• Lấy món $i$: sang $(i+1,s+a_i)$.

• Khi $i=N$: cấu hình hoàn tất; kiểm tra $s=S$.

Nếu $F(i,s)$ là số cách hoàn thành từ trạng thái hiện tại:

Công thức này có thể được thực hiện bằng đệ quy vét cạn. Chỉ khi ta lưu và dùng lại các trạng thái trùng nhau, nó mới trở thành cách giải có ghi nhớ.

Bước 6 — Viết số lần thử ngay cạnh hình.

Ghi: “$2^N$ lá; cập nhật tổng $O(1)$; thời gian $O(2^N)$; stack $O(N)$.” Nếu ở mỗi lá còn tính min/max bằng một vòng lặp, phải tính thêm chi phí đó.

Bước 7 — Tìm việc bị làm lại.

• Tổng của một đoạn được cộng lại nhiều lần → cộng dồn hoặc prefix sum.

• Cùng một tập được sinh theo nhiều thứ tự → chỉ chọn chỉ số tăng dần.

• Cùng một trạng thái tương lai xuất hiện nhiều lần → cân nhắc memoization/DP.

• $2^N$ quá lớn nhưng ghép hai phần dễ → chia đôi.

• Một nhánh đã chắc chắn hỏng → cắt tỉa với chứng minh.

2.3. Từ nháp nhận ra trạng thái đủ thông tin

Hãy tưởng tượng bạn bàn giao việc đang làm cho một người khác. Trạng thái là tờ giấy ghi đủ thông tin để người đó làm tiếp mà không cần hỏi lịch sử.

Đi đến cùng một ô nhưng đã đi qua những ô khác nhau là hai trạng thái khác nhau nếu không được thăm lại ô. Chỉ lưu (hàng, cột) sẽ đánh mất thông tin quan trọng.

2.4. Cách tìm quy luật từ những ví dụ nhỏ

Hãy thử thêm các input “khó chịu”: tất cả số bằng nhau, toàn số 0, có số âm, không có đáp án, và chỉ có một phần tử.

Ví dụ, từ [2,3,5] bạn có thể nghĩ “tổng vượt $5$ thì bỏ nhánh”. Nhưng với [8,-3], tổng tạm thời $8$ vẫn có thể trở thành $5$. Một phản ví dụ nhỏ như vậy giúp bạn phát hiện điều kiện còn thiếu trước khi code.

Mẫu nháp có thể tái sử dụng:

Ứng viên là gì:
Mỗi quyết định chọn trong tập nào:
Điều kiện hợp lệ:
Trạng thái cần giữ:
Các chuyển tiếp:
Điều kiện dừng:
Số trạng thái × chi phí mỗi trạng thái:
Có trùng lời giải không:
Cắt nhánh dựa trên chứng minh nào:

2.5. Hiểu quay lui qua việc xếp hai tấm thẻ

Bạn xếp thẻ A và B vào hai ô. Khi thử A ở ô đầu, hãy dùng B ở ô sau. Sau khi ghi nhận AB, lấy B ra rồi lấy A ra, để có thể thử B ở ô đầu và tạo BA.

Quay lui không xóa lời giải đã tìm. Nó trả bàn làm việc về trạng thái trước khi thử một nhánh.

Quy tắc cần giữ ở mọi lời gọi:

Khi một nhánh con trả về, mọi dữ liệu dùng chung của trạng thái tìm kiếm phải trở lại như trước lúc vào nhánh. Bộ đếm, đáp án tốt nhất và bản sao lời giải đã lưu là những dữ liệu kết quả, được phép giữ lại.

Khung suy nghĩ:

search(trạng thái):
    nếu đã hoàn thành: xử lý lời giải, rồi trả về
    nếu chứng minh nhánh này không cần xét: trả về
    chọn quyết định tiếp theo
    với mỗi lựa chọn còn hợp lệ:
        áp dụng lựa chọn
        search(trạng thái mới)
        hoàn tác lựa chọn

return chỉ kết thúc lời gọi hiện tại. Nó không tự dừng các hàm cha, và không tự gỡ những gì bạn đã sửa trong vector hoặc mảng dùng chung.

Tham số truyền bằng giá trị như sum tự có bản riêng cho từng lời gọi. Ngược lại, nếu sửa used[i], path hoặc bàn cờ dùng chung, hãy viết dòng hoàn tác ngay sau dòng gọi đệ quy để tránh quên.

Phần 3 — Các patterns và template C++17

Các hàm bên dưới dùng chỉ số từ 0. Dùng phần khai báo chung sau trong chương trình:

1
2
3
4#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;

bits/stdc++.h và các builtin bit là tiện ích của GCC, phù hợp môi trường GNU C17 thường dùng khi thi. Các thuật toán không cần tính năng C20.

Quy ước: tổng, hiệu trung gian và đáp án đếm phải nằm trong miền kiểu đang dùng. Khi constraints không bảo đảm điều đó, đổi kiểu hoặc cách tính theo phần 4. Không có một template “tối ưu nhất” cho mọi bài; hãy chọn mẫu có cấu trúc khớp với ứng viên của đề.

Ở các hàm sinh, visit là việc bạn muốn làm khi gặp một cấu hình, chẳng hạn kiểm tra, đếm hoặc in. Cú pháp self(self, ...) trong lambda là cách gọi đệ quy; các biến nằm trong hàm bao ngoài giúp mỗi lần gọi được khởi tạo mới, tránh sót dữ liệu giữa các test.

3.1. Duyệt cặp hoặc bộ chỉ số

Ẩn dụ: muốn thử mọi cặp bạn cùng bàn, hãy chọn bạn thứ nhất rồi chọn bạn thứ hai đứng sau bạn đó trong danh sách.

Mẫu đếm cặp chỉ số có tổng bằng target:

1
2
3
4
5
6
7
8
9ll countPairs(const vector<ll>& a, ll target) {
    int n = (int)a.size();
    ll ans = 0;
    for (int i = 0; i < n; ++i)
        for (int j = i + 1; j < n; ++j)
            if (a[i] + a[j] == target)
                ++ans;
    return ans;
}

Điều kiện i < j vừa tránh dùng một vị trí hai lần, vừa tránh đếm cả (i,j) và (j,i). Hai phần tử bằng giá trị nhưng ở hai vị trí khác nhau vẫn là hai phần tử.

Thời gian $O(N^2)$, bộ nhớ phụ $O(1)$. Với bộ ba không có thứ tự, thêm vòng lặp k = j + 1 để có i < j < k; thời gian $O(N^3)$ nếu kiểm tra $O(1)$.

3.2. Duyệt đoạn liên tiếp và cập nhật tổng

Ẩn dụ: giữ đầu trái của một đoàn tàu, rồi nối thêm từng toa vào bên phải. Muốn biết tổng số người, chỉ cần cộng số người trong toa mới.

1
2
3
4
5
6
7
8
9
10
11
12ll countSegments(const vector<ll>& a, ll target) {
    int n = (int)a.size();
    ll ans = 0;
    for (int l = 0; l < n; ++l) {
        ll sum = 0;                 // Reset cho từng đầu trái.
        for (int r = l; r < n; ++r) {
            sum += a[r];
            if (sum == target) ++ans;
        }
    }
    return ans;
}

Thời gian $O(N^2)$, bộ nhớ phụ $O(1)$. Bắt đầu r = l để có cả đoạn một phần tử. Mẫu này duyệt đoạn không rỗng và dùng được khi có số âm.

Nếu cần truy vấn nhiều tổng đoạn độc lập, đặt

thì tổng đoạn đóng $[l,r]$ bằng $pref[r+1]-pref[l]$. Kiểm tra nhanh hơn không đồng nghĩa với ít ứng viên hơn: vẫn có $\Theta(N^2)$ đoạn.

3.3. Sinh dãy, mỗi vị trí có $K$ lựa chọn

Ẩn dụ: có $N$ ô để tô màu, mỗi ô chọn một trong $K$ màu. Tô một ô, làm tiếp các ô sau, rồi thử màu khác.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16template<class Visit>
void genWords(int n, int k, Visit visit) {
    assert(n >= 0 && k >= 1);
    vector<int> x(n);
    auto dfs = [&](auto&& self, int i) -> void {
        if (i == n) {
            visit(x);
            return;
        }
        for (int v = 0; v < k; ++v) {
            x[i] = v;
            self(self, i + 1);
        }
    };
    dfs(dfs, 0);
}

Đặt k = 2 để sinh dãy nhị phân. Có $K^N$ cấu hình; với $K\ge2$, phần duyệt là $O(K^N)$ nếu visit tốn $O(1)$. Nếu visit đọc/in cả dãy, tổng thời gian là $O(NK^N)$. Riêng $K=1$ có một nhánh dài $N$, tốn $O(N)$.

Bộ nhớ phụ $O(N)$. n = 0 sinh đúng một cấu hình rỗng. Không cần hoàn tác x[i] vì nó luôn được ghi đè trước khi sử dụng; các cấu trúc như used hoặc danh sách push_back thì phải hoàn tác.

3.4. Sinh tập con bằng bitmask

Ẩn dụ: có một bảng công tắc. Công tắc thứ $i$ bật nghĩa là lấy phần tử $i$.

Ví dụ mask = 5 có biểu diễn nhị phân 101, nghĩa là lấy chỉ số $0$ và $2$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14ll countSubsets(const vector<ll>& a, ll target) {
    int n = (int)a.size();
    assert(n < 63);                // Giới hạn kiểu, không phải giới hạn chạy nhanh.
    ull limit = 1ULL << n;
    ll ans = 0;
    for (ull mask = 0; mask < limit; ++mask) {
        ll sum = 0;
        for (int i = 0; i < n; ++i)
            if ((mask >> i) & 1ULL)
                sum += a[i];
        if (sum == target) ++ans;
    }
    return ans;
}

Thời gian $O(N2^N)$, bộ nhớ phụ $O(1)$. mask = 0 là tập rỗng. Mẫu đếm theo tập chỉ số: với [1,1] và target = 1, đáp án là 2.

Nếu chỉ cần tổng, DFS mang theo tổng hoặc bảng tổng mask ở phần 4 có thể loại vòng lặp $N$ bên trong. Dùng 1ULL chỉ tránh một số lỗi kiểu; nó không làm $2^{60}$ trường hợp trở nên khả thi.

Đây là phiên bản DFS mang tổng theo, chạy $O(2^N)$ và dùng stack $O(N)$:

1
2
3
4
5
6
7
8
9ll countSubsetsDFS(const vector<ll>& a, ll target) {
    int n = (int)a.size();
    auto dfs = [&](auto&& self, int i, ll sum) -> ll {
        if (i == n) return sum == target;
        return self(self, i + 1, sum)
             + self(self, i + 1, sum + a[i]);
    };
    return dfs(dfs, 0, 0);
}

Ở đây sum truyền bằng giá trị, nên không có thao tác trừ lại sau khi gọi đệ quy. Đổi sang một biến tổng dùng chung thì phải hoàn tác đúng.

3.5. Chọn đúng $K$ phần tử

Ẩn dụ: chọn đúng ba bạn từ một hàng. Sau khi đã chọn bạn số 4, chỉ chọn tiếp những bạn đứng sau số 4, để cùng một nhóm không xuất hiện theo nhiều thứ tự.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18template<class Visit>
void genCombinations(int n, int k, Visit visit) {
    if (n < 0 || k < 0 || k > n) return;
    vector<int> chosen;
    auto dfs = [&](auto&& self, int start) -> void {
        if ((int)chosen.size() == k) {
            visit(chosen);
            return;
        }
        int need = k - (int)chosen.size();
        for (int i = start; i <= n - need; ++i) {
            chosen.push_back(i);
            self(self, i + 1);
            chosen.pop_back();      // Hoàn tác cho nhánh kế tiếp.
        }
    };
    dfs(dfs, 0);
}

i <= n - need bảo đảm còn đủ phần tử để chọn. Có $\binom NK$ cấu hình; một cận trên hữu ích là $O((K+1)\binom NK)$ khi xử lý mỗi cấu hình trong $O(K+1)$. Bộ nhớ phụ $O(K+1)$.

Với k = 0, có đúng một tổ hợp rỗng. Không nên sinh tất cả $2^N$ mask rồi lọc popcount == k nếu $K$ nhỏ và $\binom NK$ ít hơn rất nhiều.

3.6. Hoán vị và giá trị trùng nhau

Ẩn dụ: xếp các tấm thẻ thành một hàng. Nếu hai thẻ cùng ghi chữ A và không phân biệt danh tính, đổi chỗ hai thẻ A không tạo ra một hàng chữ mới.

1
2
3
4
5
6
7template<class Visit>
void genPermutations(vector<int> p, Visit visit) {
    sort(p.begin(), p.end());       // Bắt đầu từ cấu hình nhỏ nhất.
    do {
        visit(p);
    } while (next_permutation(p.begin(), p.end()));
}

Nếu mọi giá trị khác nhau, có $N!$ cấu hình. Nếu các nhóm giá trị trùng có số lượng $c_1,c_2,\ldots$, số hoán vị khác nhau là

Thời gian $O(N\log N+(N+1)P)$ khi xử lý mỗi cấu hình trong $O(N+1)$; bộ nhớ phụ $O(N)$ vì hàm nhận một bản sao vector. do...while xử lý cả cấu hình ban đầu, kể cả vector rỗng.

Nếu đề phân biệt các đồ vật dù chúng có cùng giá trị, hãy hoán vị chỉ số rồi truy cập giá trị tương ứng. Nếu cần loại nhánh ngay khi mới xếp một phần, dùng DFS với mảng đánh dấu sẽ phù hợp hơn next_permutation.

Phân biệt với chỉnh hợp: bài Permutations của MarisaOJ yêu cầu chọn và xếp $K$ phần tử trong $N$ phần tử, nên có $A_N^K=N!/(N-K)!$ cấu hình, không phải luôn là $N!$. Với kiểu DFS ở mẫu 3.12, hãy dùng các giá trị $1,\ldots,N$ và dừng khi đã chọn đủ $K$ vị trí; không cần sinh hết hoán vị dài $N$ rồi cắt lấy tiền tố.

3.7. Ghép cặp không đếm trùng

Ẩn dụ: chia một lớp có số học sinh chẵn thành các đôi. Luôn lấy người chưa ghép có số nhỏ nhất, rồi thử mọi bạn còn lại cho người đó.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25template<class Visit>
void genMatchings(int n, Visit visit) {
    assert(n >= 0 && n % 2 == 0);
    vector<char> used(n, false);
    vector<pair<int, int>> pairs;
    auto dfs = [&](auto&& self) -> void {
        int i = 0;
        while (i < n && used[i]) ++i;
        if (i == n) {
            visit(pairs);
            return;
        }
        used[i] = true;
        for (int j = i + 1; j < n; ++j) {
            if (used[j]) continue;
            used[j] = true;
            pairs.emplace_back(i, j);
            self(self);
            pairs.pop_back();
            used[j] = false;
        }
        used[i] = false;
    };
    dfs(dfs);
}

Vì luôn xử lý người chưa ghép nhỏ nhất, bạn không sinh lại cùng một cách ghép chỉ vì đổi thứ tự các cặp.

Với $N=2M$, số cách ghép là

Template có cận thời gian $O(N(2M-1)!!)$ khi visit tốn $O(N)$; bộ nhớ phụ $O(N)$. Nếu chi phí ghép phụ thuộc chỉ vào những người còn lại, có thể phát triển thành DP bitmask.

3.8. Backtracking với điều kiện hợp lệ cục bộ

Ẩn dụ: xếp đồ vào các ngăn. Vừa đặt một món đã thấy nó đụng món khác thì dừng nhánh đó ngay, không cần xếp xong mọi món rồi mới kiểm tra.

Mẫu đếm cách đặt $N$ quân hậu trên bàn $N\times N$ trống, mỗi hàng một quân:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19ll countQueens(int n) {
    assert(n >= 0);
    if (n == 0) return 1;
    vector<char> col(n), diag1(2 * n - 1), diag2(2 * n - 1);
    auto dfs = [&](auto&& self, int r) -> ll {
        if (r == n) return 1;
        ll ans = 0;
        for (int c = 0; c < n; ++c) {
            int d1 = r - c + n - 1; // Bù để không có chỉ số âm.
            int d2 = r + c;
            if (col[c] || diag1[d1] || diag2[d2]) continue;
            col[c] = diag1[d1] = diag2[d2] = true;
            ans += self(self, r + 1);
            col[c] = diag1[d1] = diag2[d2] = false;
        }
        return ans;
    };
    return dfs(dfs, 0);
}

Hai ô cùng đường chéo khi cùng $r-c$ hoặc cùng $r+c$. Mỗi phép kiểm tra trong vòng lặp là $O(1)$.

Một cận trên an toàn cho template quét đủ $N$ cột ở mỗi nút là $O(N\cdot N!)$; thực tế ít hơn do cắt xung đột đường chéo. Bộ nhớ phụ $O(N)$. Nếu chỉ duyệt các cột còn khả dụng bằng bitmask, có thể giảm công việc ở từng nút; không nên tuyên bố cắt tỉa luôn biến bài toán thành đa thức.

3.9. Nhánh cận cho bài tối ưu

Ẩn dụ: bạn đang tìm giỏ quà có giá trị lớn nhất. Một nhánh hiện được 20 điểm; ngay cả lấy toàn bộ quà còn lại cũng chỉ thêm 10 điểm. Nếu đã có giỏ 35 điểm, nhánh đó không thể thắng.

Mẫu knapsack vét cạn với trọng lượng dương, giá trị không âm, sức chứa không âm:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19ll knapsackBB(const vector<ll>& w, const vector<ll>& v, ll cap) {
    int n = (int)w.size();
    assert(v.size() == w.size() && cap >= 0);
    vector<ll> suffix(n + 1, 0);
    for (int i = n - 1; i >= 0; --i) {
        assert(w[i] > 0 && v[i] >= 0);
        suffix[i] = suffix[i + 1] + v[i];
    }
    ll best = 0;
    auto dfs = [&](auto&& self, int i, ll weight, ll value) -> void {
        best = max(best, value);
        if (i == n || value + suffix[i] <= best) return;
        if (w[i] <= cap - weight)  // Tránh cộng trọng lượng rồi mới so sánh.
            self(self, i + 1, weight + w[i], value + v[i]);
        self(self, i + 1, weight, value);
    };
    dfs(dfs, 0, 0, 0);
    return best;
}

value + suffix[i] là cận trên: giả sử được lấy mọi món còn lại mà bỏ qua sức chứa. Nó có thể quá lạc quan nhưng không được thấp hơn giá trị tốt nhất mà nhánh thực sự đạt được.

Thời gian xấu nhất vẫn $O(2^N)$, bộ nhớ phụ $O(N)$. Mẫu chỉ tìm giá trị tối ưu. Nếu phải đếm mọi cách đạt tối ưu, loại nhánh khi cận bằng best có thể làm mất các cách đồng hạng.

3.10. Meet-in-the-middle

Ẩn dụ: thay vì thử tất cả giỏ hàng gồm 40 món, chia quầy hàng thành hai nửa. Ghi các tổng có thể lấy ở mỗi nửa, rồi tìm hai tổng ghép lại thành số cần có.

Điểm quyết định là ghép nhanh. Nếu lại thử mọi tổng nửa trái với mọi tổng nửa phải, bạn quay về $2^N$.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25vector<ll> subsetSums(const vector<ll>& a, int l, int r) {
    vector<ll> sums{0};             // Có cả tập rỗng.
    sums.reserve(1ULL << (r - l));
    for (int i = l; i < r; ++i) {
        size_t oldSize = sums.size();
        for (size_t j = 0; j < oldSize; ++j)
            sums.push_back(sums[j] + a[i]);
    }
    return sums;
}

ll countSubsetsMITM(const vector<ll>& a, ll target) {
    int n = (int)a.size();
    assert(n < 63);                 // Thực tế dùng khi hai nửa đủ nhỏ.
    int mid = n / 2;
    auto left = subsetSums(a, 0, mid);
    auto right = subsetSums(a, mid, n);
    sort(right.begin(), right.end());
    ll ans = 0;
    for (ll s : left) {
        auto range = equal_range(right.begin(), right.end(), target - s);
        ans += range.second - range.first;
    }
    return ans;
}

Hai nửa mỗi nửa có khoảng $2^{N/2}$ tổng. Việc sinh tổng dùng $O(2^{N/2})$ nhờ cập nhật từ các tổng cũ, không phải quét lại từng tập.

Với cách sort và tìm nhị phân trên, thời gian là

bộ nhớ $O(2^{\lceil N/2\rceil})$. Mẫu cũng đúng với số âm nếu phép tính không tràn.

Không xóa các tổng trùng khi đang đếm tập con theo chỉ số. Hai tập con khác nhau cùng tổng vẫn là hai cách. equal_range trả về cả khoảng có giá trị bằng target - s, nên giữ đúng số cách.

3.11. Duyệt cặp kết hợp bảng tra cứu

Ẩn dụ: muốn chọn bốn món có tổng tiền đúng, hãy giữ một sổ những tổng của hai món đã xét. Khi cầm hai món mới, chỉ cần tra số tiền còn thiếu.

Mẫu tìm bốn chỉ số khác nhau có tổng bằng target:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19array<int, 4> findFourSum(const vector<ll>& a, ll target) {
    int n = (int)a.size();
    unordered_map<ll, pair<int, int>> seen;
    for (int j = 0; j < n; ++j) {
        // Trước khi tra: mọi cặp (p,q) trong seen có p < q < j.
        for (int k = j + 1; k < n; ++k) {
            ll need = target - a[j] - a[k];
            auto it = seen.find(need);
            if (it != seen.end()) {
                auto [p, q] = it->second;
                return {p, q, j, k};
            }
        }
        // Chỉ thêm sau khi đã tra xong, để không dùng lại chỉ số j.
        for (int i = 0; i < j; ++i)
            seen.emplace(a[i] + a[j], make_pair(i, j));
    }
    return {-1, -1, -1, -1};
}

Luôn có $p<q<j<k$, nên không cần xử lý va chạm chỉ số sau khi tìm được tổng. Lưu một cặp đại diện cho mỗi tổng là đủ cho yêu cầu tìm một lời giải này; không tự động đủ cho yêu cầu đếm.

Thời gian kỳ vọng $O(N^2)$ với hash, bộ nhớ tối đa $O(N^2)$. unordered_map không bảo đảm $O(1)$ trong trường hợp xấu nhất; dùng map sẽ cho $O(N^2\log N)$ và cần cân nhắc giới hạn thời gian.

3.12. Hoán vị bằng quay lui, kể cả khi có phần tử trùng

Mẫu này phù hợp khi cần kiểm tra một đoạn đầu của hoán vị trước khi xây tiếp.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25template<class Visit>
void genPermutationsDFS(vector<int> a, Visit visit) {
    sort(a.begin(), a.end());
    int n = (int)a.size();
    vector<char> used(n, false);
    vector<int> path;
    auto dfs = [&](auto&& self) -> void {
        if ((int)path.size() == n) {
            visit(path);
            return;
        }
        for (int i = 0; i < n; ++i) {
            if (used[i]) continue;
            // Cùng giá trị: dùng bản đứng trước trước, tránh nhánh trùng.
            if (i > 0 && a[i] == a[i - 1] && !used[i - 1]) continue;
            // Có thể kiểm tra ràng buộc khi nối a[i] vào path tại đây.
            used[i] = true;
            path.push_back(a[i]);
            self(self);
            path.pop_back();
            used[i] = false;
        }
    };
    dfs(dfs);
}

Vì sao có !used[i - 1]? Nếu hai bản bằng nhau đều chưa dùng, chỉ cần thử bản đứng trước ở vị trí hiện tại. Nếu bản đứng trước đã nằm trong path, ta vẫn được dùng bản tiếp theo. Cấm mọi a[i] == a[i-1] sẽ làm mất lời giải.

Với phần tử phân biệt, một cận trên cho cách quét $N$ phần tử tại mỗi nút là $O(N\cdot N!)$, chưa kể xử lý output. Tổng quát hơn, gọi $V$ là số tiền tố được thăm: chi phí là $O(N\log N+NV+\text{chi phí output})$. Bộ nhớ phụ $O(N)$. Nếu các phần tử cùng giá trị vẫn có danh tính riêng theo đề, bỏ điều kiện loại trùng.

3.13. Đường đi không lặp đỉnh

Ẩn dụ: trong một lượt đi mê cung, bạn không được bước lại chỗ đã đi. Nhưng khi quay về để thử một đường khác, những chỗ thuộc nhánh cũ phải được phép dùng lại.

Mẫu liệt kê các đường đi đơn từ s tới t trong một đồ thị nhỏ:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24template<class Visit>
void genSimplePaths(const vector<vector<int>>& g,
                    int s, int t, Visit visit) {
    int n = (int)g.size();
    assert(0 <= s && s < n && 0 <= t && t < n);
    vector<char> used(n, false);
    vector<int> path{s};
    used[s] = true;
    auto dfs = [&](auto&& self, int u) -> void {
        if (u == t) {
            visit(path);
            return;
        }
        for (int v : g[u]) {
            if (used[v]) continue;
            used[v] = true;
            path.push_back(v);
            self(self, v);
            path.pop_back();
            used[v] = false;       // Chỉ cấm trong đường hiện tại.
        }
    };
    dfs(dfs, s);
}

Giả sử các chỉ số đỉnh hợp lệ và danh sách kề không lặp cùng một đỉnh láng giềng nếu bạn muốn đếm đường theo dãy đỉnh. Đánh dấu vĩnh viễn như DFS tìm thành phần liên thông sẽ làm bỏ sót những đường đi khác.

Nếu cây tìm kiếm có $V$ nút và bậc lớn nhất là $\Delta$, cận chi phí duyệt là $O(V(\Delta+1)+\text{chi phí output})$. $V$ có thể rất lớn; trên đồ thị tổng quát số đường đi đơn có thể tăng theo giai thừa. Bộ nhớ phụ $O(N)$ ngoài đồ thị và kết quả được lưu bởi visit.

Với lưới, dùng các lựa chọn đi lên, xuống, trái, phải và kiểm tra biên/ô cấm. Với yêu cầu đi qua mọi ô hoặc đỉnh, chỉ chấp nhận ở đích khi độ dài đường đúng yêu cầu.

Cách gọi hàm sinh: sau khi có genCombinations, gọi genCombinations(4, 2, [](const vector<int>& p) { /* xử lý p */ });. Nếu lưu cấu hình, hãy sao chép vector; không giữ tham chiếu đến vector đang bị thay đổi qua các bước quay lui.

Ví dụ ghép một template thành chương trình: đặt hàm countSubsets trước main dưới đây. Đây là chương trình mẫu đếm tập con theo chỉ số, có tính tập rỗng.

1
2
3
4
5
6
7
8
9
10int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    ll target;
    cin >> n >> target;
    vector<ll> a(n);
    for (ll& x : a) cin >> x;
    cout << countSubsets(a, target) << '\n';
}

Phần 4 — Tips, tricks và bẫy ở mức ICPC

4.1. Giảm số thứ phải thử trước khi tối ưu câu lệnh

Bỏ một vòng lặp thường có ích hơn làm một câu lệnh nhanh hơn chút ít.

Nếu phải tìm các số nguyên không âm $x,y,z$ sao cho $x+y+z=S$, chỉ cần thử $x,y$ rồi tính $z=S-x-y$. Không cần thử cả ba số độc lập.

Với ước số của $X>0$, thử $d$ đến $\sqrt X$ là đủ: khi $d\mid X$, bạn biết thêm ước $X/d$. Viết d <= X / d để tránh tràn từ phép nhân d * d, và chỉ tính một lần khi $d=X/d$.

Với phân chia thành hai nhóm không tên, một tập và phần bù của nó có thể biểu diễn cùng cách chia. Có thể buộc một phần tử cố định nằm ở nhóm thứ nhất nếu việc đổi tên hai nhóm thật sự không làm thay đổi bài toán. Không áp dụng khi hai nhóm có vai trò hoặc ràng buộc khác nhau.

4.2. Tính tổng mọi mask trong $O(2^N)$

Một tập con không rỗng bằng một tập nhỏ hơn cộng thêm đúng một phần tử. Bỏ bit 1 thấp nhất:

Nếu bit bị bỏ là $b$:

1
2
3
4
5
6
7
8
9
10
11vector<ll> allMaskSums(const vector<ll>& a) {
    int n = (int)a.size();
    assert(n < 63);
    ull limit = 1ULL << n;
    vector<ll> sum(limit, 0);       // Phải kiểm tra RAM trước khi cấp phát.
    for (ull mask = 1; mask < limit; ++mask) {
        int b = __builtin_ctzll(mask); // mask luôn khác 0.
        sum[mask] = sum[mask & (mask - 1)] + a[b];
    }
    return sum;
}

Đây là đổi bộ nhớ lấy tốc độ: $O(2^N)$ thời gian và $O(2^N)$ bộ nhớ.

Chưa tính các mảng khác, stack và chi phí chương trình. Nếu chỉ cần một tổng đáp án, DFS mang tổng theo thường tiết kiệm RAM hơn.

4.3. Các thao tác bit nên thuộc

Với ull mask và chỉ số bit hợp lệ $0\le i<64$:

__builtin_ctzll(0) và __builtin_clzll(0) không có kết quả được bảo đảm; phải xử lý 0 trước. Xem tài liệu GCC về bit builtins.

Để duyệt riêng các bit đang bật, lặp với bản sao x của mask, lấy b = __builtin_ctzll(x) rồi cập nhật x &= x-1. Số lượt bằng số bit 1. Trên tất cả các mask, kỹ thuật này vẫn có tổng $N2^{N-1}$ lượt, nên không tự đổi $O(N2^N)$ thành $O(2^N)$.

Nếu cần lấy phần bù trong đúng $N$ phần tử, dùng full ^ mask hoặc (~mask) & full, với full = (1ULL << N) - 1 và $N<64$. ~mask một mình bật cả những bit ngoài miền cần xét.

4.4. Duyệt tập con của một mask

1
2
3
4
5
6
7
8
9template<class Visit>
void genSubmasks(ull mask, Visit visit) {
    ull sub = mask;
    while (true) {
        visit(sub);
        if (sub == 0) break;        // Có tính tập rỗng và tránh lặp vô hạn.
        sub = (sub - 1) & mask;
    }
}

Với một mask có $K$ bit 1, có $2^K$ submask. Nếu duyệt mọi mask rồi duyệt mọi submask của nó:

Vì mỗi phần tử có ba tình trạng: ngoài mask; trong mask nhưng ngoài submask; hoặc nằm trong submask. Đây là lý do hai vòng lặp mask/submask không đơn giản là $O(2^N)$.

Khi tách mask thành hai nhóm không có tên, sub và mask ^ sub có thể tạo hai lượt cho cùng một phép chia. Cần một quy ước đại diện, chẳng hạn buộc bit 1 thấp nhất của mask thuộc một phía, nếu bài cho phép đổi tên hai nhóm.

4.5. Cắt tỉa phải có bằng chứng

Giống như đóng một con đường: chỉ đóng khi bạn chắc chắn đi tiếp đường đó không thể tạo lời giải cần tìm.

Với tập con có cả số âm, một cách chặn an toàn hơn là tính:

Từ tổng hiện tại $s$, mọi tổng có thể hoàn thành đều nằm trong

Nếu $S$ nằm ngoài khoảng này thì cắt được. Nếu $S$ nằm trong, chưa chắc tồn tại cách chọn để đạt $S$; khoảng chỉ là điều kiện cần.

Với bài tối ưu, gọi $g$ là giá trị đã có:

• Tối thiểu hóa: nếu một cận dưới $LB$ cho giá trị cuối cùng thỏa $LB\ge best$, nhánh không thể cải thiện đáp án.

• Tối đa hóa: nếu một cận trên $UB$ thỏa $UB\le best$, nhánh không thể cải thiện đáp án.

Nếu phải đếm hoặc liệt kê các nghiệm cùng tối ưu, phải xử lý các trường hợp bằng best phù hợp. Với dữ liệu có số âm, bản thân giá trị hiện tại $g$ chưa chắc là cận đúng.

4.6. Chọn thứ tự duyệt tốt

Chọn chỗ khó trước: trong Sudoku, ô chỉ còn hai số có thể điền thường đáng thử trước ô còn tám số. Đây là ý tưởng MRV: chọn biến có ít lựa chọn còn hợp lệ nhất.

Thử lựa chọn hứa hẹn trước: với nhánh cận, tìm một lời giải tốt sớm có thể làm best mạnh hơn và cắt được nhiều nhánh sau.

Phát hiện ngõ cụt sớm: sau một lựa chọn, kiểm tra xem có biến chưa xử lý nào đã hết lựa chọn hợp lệ chưa. Kỹ thuật này thường gọi là forward checking.

Lan truyền lựa chọn bắt buộc: nếu một biến chỉ còn đúng một giá trị hợp lệ, có thể gán ngay rồi cập nhật các ràng buộc liên quan. Giống như khi đã biết mọi ghế trừ một ghế đều có người ngồi, người cuối cùng không cần thử tất cả các ghế nữa. Nếu một lựa chọn kéo theo nhiều thay đổi, hãy ghi lại những thay đổi đó và hoàn tác tất cả khi quay lui.

Các cách trên thay đổi thứ tự hoặc phát hiện bất khả thi. Chúng không cho phép bỏ các lựa chọn còn hợp lệ chỉ vì “trông không tốt”. Chi phí kiểm tra thêm cũng phải đáng so với số nhánh cắt được.

4.7. Đừng nhầm heuristic, đối xứng và chứng minh

• Thử bước đi ít ngõ ra trước trong bài quân mã là một heuristic về thứ tự; không phải bảo đảm luôn tìm được đường nếu chỉ giữ đúng một bước.

• Bàn cờ có ô cấm có thể mất đối xứng. Không tự nhân/chia đáp án cho 2 hoặc 8.

• Nếu chỉ cần tồn tại, có thể trả về khi tìm được nghiệm đầu tiên. Nếu cần nghiệm tối ưu hoặc đếm mọi nghiệm thì không được dừng theo cùng cách.

• Dừng sớm bằng bool phải truyền kết quả thành công ngược lên các hàm cha. Hãy hoàn tác dữ liệu dùng chung trước khi thoát, hoặc lưu riêng lời giải và quy định rõ trạng thái cuối của hàm.

4.8. Kết hợp tiền xử lý và cấu trúc dữ liệu

Ví dụ với F(i,sum) của bài tập con, các đường đi khác nhau có thể cùng đến một trạng thái. Nếu miền tổng đủ nhỏ, ghi nhớ có thể giảm rất nhiều việc. Nếu tổng quá lớn, bảng DP dày có thể không khả thi; phải đếm số trạng thái thực sự.

Khi đếm, hãy ghi nhớ số cách hoàn thành từ trạng thái, rồi mỗi lần đến trạng thái đó đều cộng số cách này. Không thay bằng “đã gặp thì bỏ qua”: các tiền tố khác nhau có thể tạo những nghiệm khác nhau.

Nếu cache kết quả tìm kiếm có nhánh cận, đừng lưu “không có nghiệm” chỉ vì nhánh bị cắt do best hiện tại. Bị cắt vì không thể cải thiện đáp án khác với không có cấu hình hợp lệ.

Gray code cho phép hai mask liên tiếp khác đúng một bit; với tổng tập con, có thể cộng hoặc trừ một phần tử để cập nhật. Nó không làm các điều kiện kiểm tra phức tạp khác tự nhiên trở thành $O(1)$.

4.9. Tràn số, chỉ số và khởi tạo

__int128 là phần mở rộng của compiler, không thuộc ISO C++17; chỉ dùng khi môi trường chấm hỗ trợ. Kết quả lớn hơn cả kiểu này cần một cách biểu diễn khác, chẳng hạn số nguyên lớn hoặc modulo nếu đề yêu cầu.

Một ví dụ sát lộ trình: Subset sum — MarisaOJ 346 cho $N\le20$ và $A_i\le10^{18}$. Mỗi phần tử vừa long long, nhưng tổng của 20 phần tử có thể vượt miền kiểu này. Vì vậy không được chép nguyên mẫu cộng tổng bằng long long mà bỏ qua giả định về tràn số; hãy dùng kiểu rộng hoặc kiểm tra giới hạn trước phép cộng.

Trong bài số nguyên, hạn chế dùng pow/căn số thực để quyết định dấu bằng tuyệt đối. Một giá trị gần số nguyên có thể bị làm tròn sang phía sai. Với lũy thừa dương cần chặn bởi limit, trước khi nhân p *= x, kiểm tra p > limit / x khi x > 0.

4.10. Các corner cases phải chủ động thử

1. $N=0$ nếu đề cho phép: một tập rỗng, một hoán vị rỗng, một cách chọn 0 phần tử; nhưng không có đoạn liên tiếp không rỗng.

2. $K=0$, $K=N$, $K>N$: đặc biệt với mẫu tổ hợp.

3. Mọi số bằng 0: đếm tập con tổng 0 phải tính đúng số tập chỉ số; nếu tính tập rỗng thì có $2^N$ cách.

4. Các giá trị bằng nhau: trùng giá trị không đồng nghĩa với trùng danh tính.

5. Có số âm: kiểm tra lại tất cả các điều kiện cắt theo tổng.

6. Không có đáp án hoặc mọi cấu hình đều hợp lệ: thường là dữ liệu xấu cho dừng sớm/cắt tỉa.

7. Đoạn một phần tử; đỉnh xuất phát chính là đích; ô bắt đầu bị cấm: tuân theo định nghĩa của từng đề.

8. Gọi hàm nhiều lần: không để used, best, vector đường đi hoặc cache cũ làm bẩn test sau.

9. Đệ quy rất sâu: $N=10^5$ có thể tràn stack dù số nhánh chỉ là một; xem xét cách duyệt lặp.

10. Output rất lớn: có khi chương trình chậm vì in, không phải vì sinh cấu hình.

Trong ICPC thông thường, lời giải chạy được subtask nhỏ chưa đem lại Accepted. Hãy phân biệt “brute force để kiểm tra”, “brute force cho subtask” và “thuật toán đủ chạy toàn bộ constraints”.

4.11. Những điểm nên sửa khi học từ tài liệu đính kèm

Các lưu ý trực tiếp liên quan tới phần nền tảng:

4.12. Dùng vét cạn làm “máy kiểm tra”

Vét cạn còn là cách tự bảo vệ mình khi viết thuật toán nhanh:

Viết slow(input) thật đơn giản cho input nhỏ.
Viết fast(input) theo thuật toán muốn nộp.
Sinh nhiều input nhỏ, có cả ca ngẫu nhiên và ca đặc biệt.
So sánh hai đáp án.
Nếu khác: lưu input, thu nhỏ nó và tìm nguyên nhân.

Nếu hai thuật toán được phép trả về những lời giải khác nhau, đừng so sánh chuỗi output máy móc. Hãy kiểm tra mỗi lời giải có hợp lệ không và giá trị mục tiêu có đúng không.

Có thể dùng -fsanitize=address,undefined khi kiểm tra tại máy để phát hiện lỗi bộ nhớ và một số hành vi không xác định; không dùng thời gian chạy của bản sanitizer để ước lượng time limit bản nộp.

Trước khi chuyển sang chủ đề khó hơn, hãy tự làm được các việc sau: mô tả ứng viên; viết được trạng thái; chứng minh không bỏ sót/đếm trùng; tính thời gian cả phần kiểm tra; tự viết hoàn tác; và đưa được phản ví dụ cho một điều kiện cắt sai.

Phần 5 — Lộ trình bài tập từ cơ bản đến ICPC

Ưu tiên hoàn thành toàn bộ 15 bài MarisaOJ trước. Danh sách dưới đây bao gồm tất cả các bài trong module 9 — Backtracking, không bỏ bài nào. Tôi sắp lại thứ tự học từ sinh cấu hình đến các bài cần quản lý nhiều ràng buộc; đây là thứ tự học đề xuất, không phải thứ tự hay bảng xếp hạng độ khó chính thức của MarisaOJ.

5.1. Lộ trình chính với đủ 15 bài MarisaOJ

Chặng 1 — Sinh cấu hình và không đếm trùng

Chặng 2 — Mang trạng thái theo và kiểm tra ràng buộc

Chặng 3 — Tìm kiếm với nhiều ràng buộc và lựa chọn thứ tự duyệt

5.2. Bảy bài củng cố từ Codeforces và CSES

Sau lộ trình MarisaOJ, dùng các bài dưới đây để luyện biến thể và kỹ thuật mở rộng. Các bài gắn nhãn Y cũng có trong The Ultimate Topic List của YouKn0wWho, đã được đối chiếu trong dữ liệu công khai của bản tĩnh, ở mục Backtracking hoặc Meet in the Middle.

5.3. Ba bài mở rộng từ YouKn0wWho