Quay lui và nhánh cận

Quay lui (backtracking) là cách duyệt có hệ thống mọi cấu hình của một bài toán: xây lời giải từng bước, ở mỗi bước thử lần lượt các lựa chọn còn hợp lệ, đi sâu tiếp, và khi đi hết (hoặc biết chắc nhánh này vô vọng) thì gỡ bỏ lựa chọn vừa làm để thử lựa chọn khác. Nhánh cận (branch and bound) là quay lui cho bài tối ưu, có thêm một phép ước lượng lạc quan để bỏ qua những nhánh chắc chắn không vượt được kết quả tốt nhất đang có.

Quay lui vẫn là thuật toán hàm mũ, nhưng cắt tỉa tốt có thể giảm số nút phải thăm đi hàng nghìn lần: bài 8 quân hậu có $8^8\approx 1,7·{10}^7$ cách đặt ngây thơ, $8!=40320$ hoán vị, nhưng quay lui kiểm tra sớm chỉ thăm $2057$ nút. Trang này đi từ bốn khuôn sinh cấu hình cơ bản (tập con, hoán vị, tổ hợp, phân hoạch), sang cắt tỉa theo ràng buộc, nhánh cận, ghi nhớ trạng thái, quay lui trên bitmask, và cuối cùng là cách ước lượng khi nào quay lui chạy kịp.

Ý tưởng / Trực giác

Cây tìm kiếm

Mọi thuật toán quay lui đều duyệt một cây tìm kiếm ngầm:

• gốc là cấu hình rỗng (chưa quyết định gì);
• mỗi nút ở độ sâu $i$ là một cấu hình dở dang đã quyết định $i$ thành phần đầu;
• mỗi cạnh là một lựa chọn cho thành phần tiếp theo;
• lá là cấu hình đầy đủ.

Đệ quy chính là phép duyệt theo chiều sâu (DFS) trên cây này. Vì thế quay lui đúng khi hai điều sau được đảm bảo:

1. Đầy đủ: mỗi cấu hình hợp lệ ứng với đúng một đường đi từ gốc xuống lá. Nếu một cấu hình không có đường nào thì bị sót; nếu có hai đường thì bị đếm trùng.
2. Trạng thái sạch: khi quay về nút cha, mọi thay đổi do nhánh con gây ra phải được hoàn tác, để nhánh anh em bắt đầu từ đúng trạng thái của cha.

Khuôn chung:

void backtrack(state):
    if state is a complete configuration:
        process it (count, print, update answer); return
    if this branch surely has no (better) solution: return   # prune
    for each valid choice c for the next step:
        apply c
        backtrack(new state)
        undo c                                               # backtrack

Vì sao cắt tỉa không làm sai

Cắt một nút nghĩa là bỏ toàn bộ cây con của nó. Việc này an toàn khi và chỉ khi ta chứng minh được cây con đó không chứa lá nào cần thiết:

• Cắt theo ràng buộc (kiểm tra sớm): cấu hình dở dang đã vi phạm ràng buộc thì mọi cách hoàn thiện nó cũng vi phạm (vd hai quân hậu đã ăn nhau thì đặt thêm quân nào cũng vậy). Điều kiện là ràng buộc có tính "đơn điệu": vi phạm ở cấu hình con thì vi phạm ở mọi cấu hình mở rộng.
• Cắt theo cận (nhánh cận): với bài tìm max, nếu một cận trên lạc quan của mọi lá trong cây con vẫn $\le$ kết quả tốt nhất đã có, thì cây con không cải thiện được đáp án. Cận phải không bao giờ đánh giá thấp giá trị thật (với bài tìm min thì là cận dưới không bao giờ đánh giá cao). Cận càng sát thì cắt càng nhiều, nhưng một cận "sát" mà sai thì cắt nhầm và cho đáp số sai.
• Cắt theo đối xứng / trạng thái trùng: nếu hai nút dẫn tới cùng một bài toán con thì chỉ cần giải một lần (ghi nhớ), hoặc chỉ thử một đại diện (vd các phần tử bằng nhau, các nhóm rỗng hoán đổi được).

Bốn khuôn sinh cấu hình

Để ý hai mẹo tránh đếm trùng:

• Tổ hợp chỉ sinh dãy tăng dần, nên $\{1,2\}$ và $\{2,1\}$ không bị sinh hai lần. Vòng lặp dừng ở $n-(\text{số còn thiếu})+1$ để còn đủ chỗ cho các phần tử sau.
• Phân hoạch mã hóa bằng dãy "nhãn nhóm" $b_1{b}_2\dots b_n$ với $b_1=1$ và $b_i\le max(b_1..b_{i-1})+1$ (restricted growth string). Phần tử mới chỉ được vào một nhóm đã có hoặc mở đúng một nhóm mới có nhãn kế tiếp, nhờ vậy việc đổi tên nhóm không tạo ra phân hoạch trùng.

Số Bell tăng rất nhanh: $B_{10}=115975$, $B_{12}=4213597$, $B_{13}=27644437$, $B_{15}\approx 1,4·{10}^9$.

Ví dụ chạy tay: cây hoán vị với $n=3$

                         ( )                       độ sâu 0: 1 nút
            /             |             \
          (1)            (2)            (3)        độ sâu 1: 3 nút
         /   \          /   \          /   \
     (1,2)  (1,3)   (2,1)  (2,3)   (3,1)  (3,2)    độ sâu 2: 6 nút
       |      |       |      |       |      |
    (1,2,3)(1,3,2) (2,1,3)(2,3,1) (3,1,2)(3,2,1)   độ sâu 3: 6 lá

Tổng $1+3+6+6=16$ nút, khớp công thức $\frac{3!}{3!}+\frac{3!}{2!}+\frac{3!}{1!}+\frac{3!}{0!}$. Thứ tự DFS thăm lá chính là thứ tự từ điển, vì ở mỗi nút ta thử giá trị từ nhỏ đến lớn.

Theo dõi mảng used khi đi nhánh trái cùng rồi quay lui:

gọi              cur        used[1..3]    việc làm
go()             []         F F F         thử v=1
 go()            [1]        T F F         thử v=2 (v=1 đã dùng)
  go()           [1,2]      T T F         thử v=3
   go()          [1,2,3]    T T T         đủ n phần tử: in 1 2 3
  gỡ v=3         [1,2]      T T F         hết lựa chọn, trở về
 gỡ v=2          [1]        T F F         thử v=3
  go()           [1,3]      T F T         thử v=2
   go()          [1,3,2]    T T T         in 1 3 2
  ...

Nếu quên dòng used[v] = false khi gỡ, sau lá đầu tiên cả ba giá trị đều bị coi là "đã dùng" mãi mãi và chương trình chỉ in đúng một hoán vị.

Cài đặt bốn khuôn

#include <bits/stdc++.h>
using namespace std;

int n, k;
vector<int> cur;          // current partial configuration
vector<bool> used;        // used[v]: value v already placed (permutations)

void printCur() {
    for (int x : cur) cout << x << ' ';
    cout << '\n';
}

// Subsets of {1..n}: at depth i decide "skip i" or "take i".
void subsets(int i) {
    if (i > n) { printCur(); return; }
    subsets(i + 1);                 // branch 1: skip i
    cur.push_back(i);               // branch 2: take i
    subsets(i + 1);
    cur.pop_back();                 // undo before returning
}

// Permutations of {1..n}: position by position, try every unused value.
void permutations() {
    if ((int)cur.size() == n) { printCur(); return; }
    for (int v = 1; v <= n; v++) {
        if (used[v]) continue;
        used[v] = true; cur.push_back(v);
        permutations();
        used[v] = false; cur.pop_back();
    }
}

// k-combinations of {1..n} in increasing order; start = smallest allowed value.
void combinations(int start) {
    if ((int)cur.size() == k) { printCur(); return; }
    int need = k - (int)cur.size();
    for (int v = start; v <= n - need + 1; v++) {   // leave room for the rest
        cur.push_back(v);
        combinations(v + 1);
        cur.pop_back();
    }
}

// Set partitions of {1..n}: cur[i] = block id of element i+1 (restricted growth string).
void partitions(int i, int blocks) {
    if (i == n) { printCur(); return; }
    for (int b = 1; b <= blocks + 1; b++) {         // join an old block or open a new one
        cur.push_back(b);
        partitions(i + 1, max(blocks, b));
        cur.pop_back();
    }
}

int main() {
    n = 3; k = 2;
    used.assign(n + 1, false);
    cout << "subsets:\n";      subsets(1);
    cout << "permutations:\n"; permutations();
    cout << "combinations:\n"; combinations(1);
    cout << "partitions:\n";   partitions(0, 0);
}

Với $n=3$, phần phân hoạch in ra 1 1 1, 1 1 2, 1 2 1, 1 2 2, 1 2 3: đúng $B_3=5$ phân hoạch.

Python: hàm lồng nhau truy cập danh sách của hàm ngoài; nhớ sao chép cur[:] khi lưu kết quả, vì cur còn bị sửa tiếp.

import sys
sys.setrecursionlimit(10000)

def permutations(n):
    cur, used, out = [], [False] * (n + 1), []

    def go():
        if len(cur) == n:
            out.append(cur[:])          # copy: cur keeps changing
            return
        for v in range(1, n + 1):
            if not used[v]:
                used[v] = True
                cur.append(v)
                go()
                cur.pop()
                used[v] = False

    go()
    return out

def partitions(n):
    cur, out = [], []

    def go(i, blocks):
        if i == n:
            out.append(cur[:])
            return
        for b in range(1, blocks + 2):  # join an old block or open a new one
            cur.append(b)
            go(i + 1, max(blocks, b))
            cur.pop()

    go(0, 0)
    return out

print(permutations(3))
print(len(partitions(5)))  # Bell number B5 = 52

Khi chỉ cần liệt kê tập con mà không cắt tỉa, duyệt for mask in range(1 << n) thường gọn hơn đệ quy. Đệ quy thắng thế khi cần cắt tỉa giữa chừng: vòng lặp mặt nạ luôn đi hết $2^n$ trường hợp.

Cắt tỉa theo ràng buộc: bài N quân hậu

Bài toán. Đặt $n$ quân hậu lên bàn cờ $n\times n$ sao cho không hai quân nào ăn nhau (cùng hàng, cột hoặc đường chéo). Đếm số cách.

Thiết kế cây tìm kiếm. Mỗi hàng có đúng một quân, nên quyết định theo hàng: ở hàng $r$ chọn cột cho quân hậu. Chỉ riêng việc chọn "đơn vị quyết định" này đã giảm cây từ $\left(\genfrac{}{}{0ex}{}{n^2}{n}\right)$ xuống $n^n$. Mỗi cột cũng dùng đúng một lần nên thực chất là sinh hoán vị ($n!$). Cuối cùng, kiểm tra sớm: chỉ đặt quân vào cột không bị quân nào ở các hàng trên khống chế, thay vì đặt xong cả $n$ quân rồi mới kiểm tra.

Ví dụ chạy tay với $n=4$

Ký hiệu Q là quân hậu, x là ô bị khống chế ở hàng đang xét.

Nhánh cột 0 ở hàng 0:

 hàng 0: Q . . .        hàng 1 chỉ còn cột 2, 3
 hàng 1: x x . .

 (0,0)(1,2):            (0,0)(1,3):
 Q . . .                Q . . .
 . . Q .                . . . Q
 x x x x  <- hết chỗ    x . x x   -> đặt (2,1)
          CẮT           . Q . .
                        x x x x  <- hàng 3 hết chỗ: CẮT

Nhánh cột 1 ở hàng 0:

 . Q . .      hàng 1: chỉ còn cột 3
 . . . Q      hàng 2: chỉ còn cột 0
 Q . . .      hàng 3: chỉ còn cột 2
 . . Q .      => lời giải [1, 3, 0, 2]

Nhánh cột 2 và cột 3 đối xứng với cột 1 và cột 0, cho thêm lời giải $[2,0,3,1]$. Toàn bộ cây chỉ có $17$ nút (kể cả gốc), trong khi sinh đủ $4!=24$ hoán vị rồi kiểm tra cần $1+4+12+24+24=65$ nút.

Quay lui trên bitmask

Thay vì mảng đánh dấu, lưu ba mặt nạ bit cho hàng đang xét: cols (cột đã có hậu), d1 và d2 (ô bị hai loại đường chéo khống chế). Tập cột an toàn là ~(cols | d1 | d2), lấy từng bit thấp nhất bằng free & -free. Khi xuống hàng dưới, đường chéo d1 dịch sang trái một bit, d2 dịch sang phải một bit. Mỗi thao tác là $O(1)$ và việc "gỡ" là tự động: mặt nạ được truyền theo giá trị, cha không bị sửa.

#include <bits/stdc++.h>
using namespace std;

int n;
long long solutions = 0;

// cols, d1, d2: bitmasks of columns / diagonals attacked on the current row.
void place(int row, int cols, int d1, int d2) {
    if (row == n) { solutions++; return; }
    int full = (1 << n) - 1;
    int free = full & ~(cols | d1 | d2);        // safe columns on this row
    while (free) {
        int bit = free & -free;                  // lowest safe column
        free ^= bit;
        // shift diagonals by one when moving to the next row
        place(row + 1, cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1);
    }
}

int main() {
    cin >> n;
    place(0, 0, 0, 0);
    cout << solutions << "\n";
}

def count_queens(n):
    full = (1 << n) - 1

    def place(row, cols, d1, d2):
        if row == n:
            return 1
        total = 0
        free = full & ~(cols | d1 | d2)     # safe columns on this row
        while free:
            bit = free & -free
            free ^= bit
            total += place(row + 1, cols | bit, ((d1 | bit) << 1) & full, (d2 | bit) >> 1)
        return total

    return place(0, 0, 0, 0)

print(count_queens(int(input())))

Số nút thực tế: $n=8$ thăm $2057$ nút ($92$ lời giải), $n=12$ thăm khoảng $8,6·{10}^5$ nút ($14200$ lời giải). Bản C++ đếm xong $n=14$ trong khoảng $0,15$ giây, $n=15$ khoảng $1$ giây; bản Python xong $n=12$ trong khoảng $0,2$ giây.

Sudoku và tô màu: chọn biến khó nhất trước

Sudoku, tô màu đồ thị bằng $k$ màu, xếp lịch có ràng buộc... đều là bài toán thỏa mãn ràng buộc: gán giá trị cho các biến sao cho mọi ràng buộc đều thỏa. Hai cải tiến có tác động lớn nhất:

1. Tập ứng viên bằng bitmask. Với mỗi hàng, cột, khối $3\times 3$ giữ mặt nạ chữ số đã dùng; ứng viên của ô $(r,c)$ là phần bù của row[r] | col[c] | box[b]. Với tô màu: mặt nạ màu đã dùng bởi các đỉnh kề.
2. Chọn biến ít lựa chọn nhất (MRV, minimum remaining values). Không điền ô theo thứ tự cố định mà điền ô ít ứng viên nhất. Ô có $0$ ứng viên báo bế tắc ngay lập tức (cắt sớm); ô có $1$ ứng viên được điền mà không rẽ nhánh. Thứ tự này không đổi tập lời giải, chỉ đổi hình dạng cây: rẽ nhánh ở chỗ hẹp nhất thì cây nhỏ nhất.

#include <bits/stdc++.h>
using namespace std;

int g[9][9];
int rowUsed[9], colUsed[9], boxUsed[9];   // bit d set: digit d+1 already used

int box(int r, int c) { return r / 3 * 3 + c / 3; }

void setDigit(int r, int c, int d, bool on) {   // place (on) or remove (off) digit d
    int bit = 1 << (d - 1);
    if (on) { rowUsed[r] |= bit; colUsed[c] |= bit; boxUsed[box(r, c)] |= bit; }
    else { rowUsed[r] &= ~bit; colUsed[c] &= ~bit; boxUsed[box(r, c)] &= ~bit; }
    g[r][c] = on ? d : 0;
}

bool solve() {
    // Pick the empty cell with the fewest candidates (most constrained first).
    int br = -1, bc = -1, bestMask = 0, bestCnt = 10;
    for (int r = 0; r < 9; r++)
        for (int c = 0; c < 9; c++) {
            if (g[r][c]) continue;
            int cand = 0x1FF & ~(rowUsed[r] | colUsed[c] | boxUsed[box(r, c)]);
            int cnt = __builtin_popcount(cand);
            if (cnt < bestCnt) { bestCnt = cnt; br = r; bc = c; bestMask = cand; }
        }
    if (br == -1) return true;          // no empty cell: solved
    if (bestCnt == 0) return false;     // dead cell: prune immediately
    for (int m = bestMask; m; m &= m - 1) {
        int d = __builtin_ctz(m) + 1;
        setDigit(br, bc, d, true);
        if (solve()) return true;
        setDigit(br, bc, d, false);     // undo
    }
    return false;
}

int main() {
    for (int r = 0; r < 9; r++) {
        string s; cin >> s;             // 9 chars, '.' or '0' for an empty cell
        for (int c = 0; c < 9; c++)
            if (s[c] >= '1' && s[c] <= '9') {
                int d = s[c] - '0', bit = 1 << (d - 1);
                if ((rowUsed[r] | colUsed[c] | boxUsed[box(r, c)]) & bit) {
                    cout << "NO SOLUTION\n"; return 0;   // duplicate given digit
                }
                setDigit(r, c, d, true);
            }
    }
    if (!solve()) { cout << "NO SOLUTION\n"; return 0; }
    for (int r = 0; r < 9; r++) {
        for (int c = 0; c < 9; c++) cout << g[r][c];
        cout << '\n';
    }
}

Chương trình giải các đề sudoku "khó nhất" thường gặp (chỉ $21$ ô cho trước) trong vài phần trăm giây. Cùng khung đó áp dụng cho tô màu: biến là đỉnh, ứng viên là các màu chưa bị đỉnh kề dùng, chọn đỉnh ít màu khả dụng nhất; thêm mẹo đối xứng "chỉ được dùng màu mới có số hiệu nhỏ nhất chưa dùng" (giống restricted growth string ở trên) để không thử lại các cách tô chỉ khác nhau bởi việc đổi tên màu.

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

Với bài tìm max, giữ biến best là kết quả tốt nhất đã tìm thấy. Tại mỗi nút, tính một cận trên lạc quan $UB$ của mọi lá trong cây con: giá trị hiện có cộng với ước lượng "quá tay" của phần còn lại. Nếu $UB\le best$ thì bỏ cả cây con.

Hai yếu tố quyết định hiệu quả:

• Cận sát. Cận càng gần giá trị thật thì càng nhiều nhánh bị cắt. Cận thường lấy từ một bài toán nới lỏng dễ giải hơn: bỏ bớt ràng buộc, cho phép lấy phân số, bỏ điều kiện "mỗi phần tử dùng một lần"...
• Tìm nghiệm tốt sớm. $best$ càng lớn sớm thì phép cắt càng mạnh. Vì vậy sắp xếp các lựa chọn để thử lựa chọn hứa hẹn nhất trước, hoặc khởi tạo $best$ bằng một lời giải tham lam trước khi quay lui.

Ví dụ: cái túi 0/1 với cận phân số

Có $n$ đồ vật, vật $i$ nặng $w_i$ và giá trị $v_i$; chọn tập vật tổng khối lượng $\le W$, tổng giá trị lớn nhất. Khi $W$ rất lớn (vd ${10}^9$) và $n\le 40$ đến $60$, quy hoạch động theo khối lượng không dùng được, còn nhánh cận thường chạy rất nhanh.

• Thứ tự: sắp vật theo mật độ $v_i/w_i$ giảm dần, thử nhánh "lấy" trước nhánh "bỏ".
• Cận trên: bài cái túi phân số (được lấy một phần của vật) giải đúng bằng tham lam theo mật độ, và giá trị của nó luôn $\ge$ giá trị cái túi 0/1 trên cùng phần còn lại. Đây là một cận lạc quan hợp lệ.

#include <bits/stdc++.h>
using namespace std;

struct Item { long long w, v; };

int n;
long long cap, best = 0;
vector<Item> items;

// Optimistic bound: fill the remaining capacity greedily from item i on,
// allowing a fraction of the first item that does not fit (fractional knapsack).
double upperBound(int i, long long room, long long value) {
    double bound = value;
    for (; i < n && items[i].w <= room; i++) {
        room -= items[i].w;
        bound += items[i].v;
    }
    if (i < n) bound += (double)items[i].v * room / items[i].w;
    return bound;
}

void go(int i, long long room, long long value) {
    best = max(best, value);                         // every node is a valid solution
    if (i == n) return;
    if (upperBound(i, room, value) <= best) return;  // cannot beat best: prune
    if (items[i].w <= room)                          // try "take" first: good answers early
        go(i + 1, room - items[i].w, value + items[i].v);
    go(i + 1, room, value);                          // then "skip"
}

int main() {
    cin >> n >> cap;
    items.resize(n);
    for (auto& it : items) cin >> it.w >> it.v;
    // Sort by value density so the bound is tight and good items are tried first.
    sort(items.begin(), items.end(), [](const Item& a, const Item& b) {
        return a.v * b.w > b.v * a.w;
    });
    go(0, cap, 0);
    cout << best << "\n";
}

Ví dụ chạy tay

$W=10$, bốn vật (đã sắp theo mật độ giảm dần):

vật      A      B      C      D
w        3      4      6      5
v       50     40     30     10
v/w    16.7   10     5      2

Mỗi nút ghi (vật đang xét, sức chứa còn lại, giá trị hiện tại), $UB$ và $best$ sau khi thăm nút:

(A,10,0)  UB = 50+40 + 30*3/6 = 105      best = 0
 ├─ lấy A: (B,7,50)   UB = 105            best = 50
 │   ├─ lấy B: (C,3,90)  UB = 90 + 30*3/6 = 105   best = 90
 │   │   └─ C không vừa, bỏ C: (D,3,90)  UB = 90 + 10*3/5 = 96
 │   │       └─ D không vừa, bỏ D: lá, giá trị 90
 │   └─ bỏ B: (C,7,50)   UB = 50+30 + 10*1/5 = 82 <= 90   CẮT
 └─ bỏ A: (B,10,0)   UB = 40+30 = 70 <= 90                 CẮT

Chỉ $7$ nút được thăm, so với $31$ nút của cây nhị phân đầy đủ $4$ tầng. Nhờ thử "lấy" trước theo mật độ, lời giải tối ưu $90$ (vật A và B) được tìm ra ngay ở nhánh đầu tiên, và hai nhánh lớn còn lại bị cắt bởi cận. Trên $60$ vật ngẫu nhiên, số nút được thăm dao động từ vài trăm tới vài chục nghìn tùy dữ liệu, thay vì $2^{60}$: khi $w$, $v$ độc lập trong $[1,{10}^5]$ chỉ khoảng một vài trăm nút; khi giá trị tương quan mạnh với khối lượng ($v=w+$ một số ngẫu nhiên nhỏ) cận kém sắc hơn và cần từ vài nghìn tới vài chục nghìn nút.

Với bài tìm min mọi thứ đổi chiều: dùng cận dưới lạc quan $LB$ (vd chi phí đã đi + tổng các cạnh rẻ nhất có thể dùng cho phần còn lại) và cắt khi $LB\ge best$. Ví dụ quen thuộc là bài người du lịch (TSP): cận dưới = chi phí đường đã đi + (số thành phố chưa thăm) $\times$ (cạnh nhỏ nhất của đồ thị).

Ghi nhớ trạng thái: chia tập thành $k$ phần tổng bằng nhau

Bài toán. Cho $n\le 20$ số nguyên dương, có chia được thành $k$ nhóm có tổng bằng nhau không?

Quay lui ngây thơ "phần tử $i$ vào nhóm nào" có $k^n$ lá. Các kỹ thuật cắt tỉa, mỗi cái đều có lý do đúng riêng:

1. Điều kiện cần: tổng chia hết cho $k$ và không phần tử nào lớn hơn $target=sum/k$.
2. Lấp từng nhóm một: lấp đầy nhóm hiện tại tới đúng $target$ rồi mới mở nhóm sau. Khi đó tập phần tử đã dùng (mask) xác định luôn tải của nhóm đang lấp ($=\text{tổng}(mask)modtarget$).
3. Ghi nhớ trạng thái thất bại: vì mask xác định toàn bộ phần còn lại của bài toán, nếu từ mask đã từng thất bại thì mọi lần gặp lại cũng thất bại. Mảng failed[mask] đưa số trạng thái về tối đa $2^n$. Đây chính là cầu nối sang DP bitmask: quay lui + ghi nhớ theo mặt nạ là DP bitmask viết theo kiểu đệ quy.
4. Phần tử lớn trước: sắp giảm dần; phần tử lớn khó xếp nhất nên xếp trước để thất bại lộ ra sớm, ở gần gốc.
5. Phá đối xứng: nếu nhóm đang rỗng mà phần tử đầu tiên thử vào đó thất bại thì dừng hẳn (mọi nhóm rỗng như nhau, phần tử đó rồi cũng phải vào một nhóm rỗng nào đó); và các giá trị bằng nhau chỉ thử một bản.

#include <bits/stdc++.h>
using namespace std;

int n, k;
long long target;
vector<long long> a;
vector<char> failed;     // failed[mask] = 1: the items in mask can never be completed

// mask: items already used. Buckets are filled one at a time, so the load of the
// current bucket is determined by mask (sum of mask modulo target).
bool fill(int mask, long long load) {
    if (mask == (1 << n) - 1) return true;
    if (failed[mask]) return false;                // state explored before: skip
    for (int i = 0; i < n; i++) {
        if (mask >> i & 1) continue;
        if (load + a[i] > target) continue;         // does not fit into this bucket
        // equal values are interchangeable: try only the first unused copy
        if (i > 0 && a[i] == a[i - 1] && !(mask >> (i - 1) & 1)) continue;
        long long next = load + a[i];
        if (fill(mask | 1 << i, next == target ? 0 : next)) return true;
        if (load == 0) break;   // the first item of an empty bucket failed: no other choice helps
    }
    failed[mask] = 1;
    return false;
}

int main() {
    cin >> n >> k;
    a.resize(n);
    long long sum = 0;
    for (auto& x : a) { cin >> x; sum += x; }
    sort(a.rbegin(), a.rend());                     // large items first: fail early
    if (sum % k != 0 || a[0] > sum / k) { cout << "NO\n"; return 0; }
    target = sum / k;
    failed.assign(1 << n, 0);
    cout << (fill(0, 0) ? "YES" : "NO") << "\n";
}

Ví dụ: 4 3 2 3 5 2 1 với $k=4$ có tổng $20$, $target=5$, chia được thành $\{5\},\{4,1\},\{3,2\},\{3,2\}$. Còn 1 2 3 4 với $k=3$ có tổng $10$ không chia hết cho $3$ nên trả lời NO ngay.

Độ phức tạp

• Thời gian = (số nút được thăm) $\times$ (chi phí mỗi nút). Không cắt tỉa thì số nút là con số trong bảng bốn khuôn ở trên: $O(2^n)$ nút cho tập con, $O(n!)$ cho hoán vị, $O(B_n)$ cho phân hoạch. Chi phí mỗi nút là $O(1)$ nếu cập nhật trạng thái tăng dần (bitmask, mảng đánh dấu), hoặc $O(n)$ nếu mỗi lá phải sao chép/in cấu hình, cho tổng $O(n·2^n)$, $O(n·n!)$...
• Cắt tỉa không đổi cận trên lý thuyết trong trường hợp xấu nhất, nhưng thực tế thường giảm số nút nhiều bậc (8 quân hậu: $2057$ nút so với $40320$ lá của cây hoán vị). Vì khó chứng minh, hãy đo số nút trên test lớn nhất tự sinh, gồm cả test khiến cắt tỉa kém (vd không có lời giải, mọi giá trị bằng nhau).
• Ghi nhớ chặn số trạng thái phân biệt: bài chia $k$ nhóm có tối đa $2^n$ mặt nạ, mỗi mặt nạ duyệt $O(n)$ lựa chọn, tổng $O(n·2^n)$ thời gian và $O(2^n)$ bộ nhớ.
• Bộ nhớ của quay lui thuần chỉ là $O(\text{độ sâu})$: ngăn xếp đệ quy cộng cấu hình dở dang, vì chỉ lưu một đường đi từ gốc. Đây là lợi thế lớn so với DP khi không gian trạng thái khổng lồ.

Khi nào quay lui chạy kịp?

Với khoảng ${10}^8$ phép tính đơn giản mỗi giây (C++), xem thêm Ước lượng giới hạn:

Quy tắc ngón tay cái: thấy $n\le 10$ nghĩ tới hoán vị; $n\le 20$ nghĩ tới tập con hoặc DP bitmask; $n\le 40$ nghĩ tới gặp nhau ở giữa; lớn hơn nữa mà vẫn là tìm kiếm thì cần nhánh cận với cận thật tốt, và nên có phương án dự phòng.

Chiến thuật VOI: quay lui là công cụ gom subtask

Đề VOI chấm theo subtask, và gần như mọi bài đều có subtask $n$ nhỏ ($n\le 8$, $10$, $20$) dành cho vét cạn. Trong phòng thi:

1. Viết quay lui trước cho mọi bài chưa nghĩ ra lời giải đầy đủ. Nó thường chỉ mất 10 đến 15 phút và đảm bảo điểm của subtask nhỏ nhất.
2. Dùng nó làm "trình chấm": lời giải tối ưu viết sau được so sánh với quay lui trên hàng nghìn test ngẫu nhiên nhỏ (đối chiếu kiểu stress test, xem Kỹ thuật debug). Đây là cách rẻ nhất để bắt lỗi sai của lời giải chính.
3. Nâng cấp dần: thêm kiểm tra sớm, sắp thứ tự thử, nhánh cận, ghi nhớ; mỗi bước có thể mở thêm một subtask trung gian.
4. Khi quay lui có ghi nhớ bắt đầu "trông giống" DP, hãy dừng lại hỏi: trạng thái ghi nhớ gồm những gì, có bao nhiêu trạng thái? Rất nhiều lời giải DP bitmask của VOI được phát hiện đúng theo con đường này.

Xem thêm bản đồ kiến thức và lộ trình ở Ôn thi VOI.

⚠️ Lỗi thường gặp

• Quên hoàn tác trạng thái. Đánh dấu used[v] = true nhưng không trả lại false, hoặc push_back mà không pop_back. Triệu chứng: chỉ in ra một vài cấu hình, hoặc số cấu hình ít bất thường. Cách tránh: viết cặp "áp dụng / gỡ" ngay cạnh nhau, đối xứng quanh lời gọi đệ quy; hoặc truyền trạng thái theo giá trị (như các mặt nạ trong bài N quân hậu) để không cần gỡ.
• Gỡ không đúng khi có return sớm. Nếu hàm trả về true ngay khi tìm thấy lời giải (sudoku) thì không gỡ là cố ý, để giữ lời giải. Nhưng nếu hàm đếm (hoặc tìm tất cả) mà lại return giữa vòng lặp trước khi gỡ, trạng thái bị hỏng cho các nhánh sau. Phân biệt rõ hai chế độ "tìm một" và "duyệt hết".
• Cận sai chiều hoặc không hợp lệ. Cận trên phải lớn hơn hoặc bằng mọi giá trị trong cây con; dùng một cận "đẹp" nhưng có thể đánh giá thấp (vd lời giải tham lam của phần còn lại thay vì cái túi phân số) sẽ cắt nhầm nhánh tối ưu. Triệu chứng: đúng ví dụ, sai vài test ẩn, đáp số hơi nhỏ hơn đúng. Kiểm chứng: tạm tắt dòng cắt và so kết quả trên test nhỏ.
• Cắt bằng <= khi cần các nghiệm hòa. Cắt với UB <= best là đúng khi chỉ cần giá trị tối ưu, và vẫn đúng khi cần in lời giải nhỏ nhất theo thứ tự từ điển nếu DFS duyệt đúng thứ tự từ điển và chỉ cập nhật best khi gặp giá trị lớn hơn hẳn (nghiệm hòa tìm sau luôn lớn hơn về từ điển). Nhưng nếu đề yêu cầu đếm số cách đạt tối ưu, hoặc cần nghiệm nhỏ nhất theo từ điển trong khi thứ tự duyệt không phải thứ tự từ điển (vd cái túi sắp theo mật độ), thì cắt ở <= sẽ bỏ sót các nghiệm bằng giá trị; phải dùng UB < best.
• Sinh trùng cấu hình. Sinh tổ hợp mà không ép tăng dần, phân hoạch mà cho phép nhãn nhóm tùy ý, hoặc thử cả các phần tử bằng nhau như khác nhau. Triệu chứng: bài đếm cho kết quả gấp $k!$ hoặc nhiều hơn đáp án; bài tìm kiếm chậm bất thường. Cách tránh: chọn biểu diễn chính tắc (dãy tăng, restricted growth string) và phá đối xứng.
• Ghi nhớ trạng thái không đầy đủ. failed[mask] chỉ đúng khi mask xác định hoàn toàn bài toán con còn lại. Nếu kết quả còn phụ thuộc thêm tham số khác (vd tải của nhóm khi không lấp từng nhóm một, hoặc vị trí hiện tại trong bài đường đi), phải đưa tham số đó vào khóa ghi nhớ, nếu không sẽ trả lời sai.
• Kiểm tra muộn. Chỉ kiểm tra ràng buộc ở lá (sinh đủ $n!$ hoán vị rồi mới xem có hợp lệ) biến bài chạy $0,01$ giây thành chạy vài phút. Luôn kiểm tra ràng buộc ngay khi thành phần liên quan vừa được quyết định.
• Tràn ngăn xếp / giới hạn đệ quy trong Python. Python mặc định giới hạn khoảng $1000$ tầng; quay lui sâu cần sys.setrecursionlimit. Python cũng chậm hơn C++ khoảng 30 đến 100 lần, nên ngưỡng $n$ trong bảng trên giảm đi đáng kể (vd $2^{20}$ nút đã mất cỡ một giây).
• Sao chép cấu hình ở mỗi nút. Truyền vector theo giá trị hoặc cur[:] ở mọi lời gọi khiến mỗi nút tốn $O(n)$ thay vì $O(1)$. Chỉ sao chép khi lưu kết quả ở lá.

Biến thể / Mở rộng

• Gặp nhau ở giữa: khi $n$ khoảng $30$ đến $40$, tách tập thành hai nửa, quay lui sinh mọi cấu hình của từng nửa rồi ghép bằng sắp xếp / tìm kiếm nhị phân. Xem Meet in the middle.
• DP bitmask: quay lui có ghi nhớ theo tập đã dùng chính là DP bitmask; viết dạng bảng lặp thường nhanh hơn và dễ phân tích hơn. Xem DP bitmask.
• Iterative deepening (IDDFS): khi cần lời giải có ít bước nhất mà BFS tốn quá nhiều bộ nhớ, chạy DFS với giới hạn độ sâu $d=1,2,3,\dots$; kết hợp với cận dưới số bước còn lại thành IDA*. Hợp với các bài xếp hình, trò chơi trượt ô.
• Sinh cấu hình kế tiếp không đệ quy: next_permutation trong C++ hoặc itertools.permutations, itertools.combinations trong Python, khi không cần cắt tỉa giữa chừng.
• Bitset tăng tốc kiểm tra: khi mỗi nút phải kiểm tra tương thích với nhiều phần tử (vd tìm clique lớn nhất), lưu tập ứng viên dạng bitset để giao hai tập trong $O(n/64)$.

Bài tập luyện

Luyện kỹ thuật

• Phân Giống Bò (assign) (Học việc) gán một trong $3$ giống cho $N\le 15$ con bò rồi đếm cách thỏa mọi quan hệ "cùng/khác giống": khuôn $3^n$ cơ bản, luyện kiểm tra ràng buộc ngay khi con bò thứ hai của mỗi quan hệ vừa được gán.
• Đường Đi Hamilton (grazing) (Học việc) đếm đường đi qua mọi ô trống của lưới $5\times 5$: DFS đánh dấu ô khi vào và bỏ đánh dấu khi ra, cắt ngay khi chạm ô đích mà chưa đi hết các ô.
• Móng ngựa (hshoe) (Nghiệp dư) đi trên lưới không lặp ô để thu chuỗi (((...))) dài nhất: trạng thái đệ quy gồm số ( và số ) đã thu, cắt ngay khi gặp ( sau ) hoặc số ) vượt số (.
• QUIDDITCH Đội Quidditch (quidditch) (Nâng cao) chọn $7$ cầu thủ từ $N\le 20$ ứng viên cho $4$ loại vị trí để tổng kỹ năng lớn nhất: quay lui gán từng suất vị trí với nhánh cận, hoặc ghi nhớ theo mặt nạ số suất đã lấp để chuyển sang DP.
• Trò chơi XOR (xorgame) (Kỳ cựu) chọn dãy $u\le 30$ thao tác, cây đầy đủ có $2^{30}$ lá: cần nhận ra hai lần XOR liên tiếp tự triệt tiêu để cắt nhánh, và nhờ đó có thể cập nhật đáp án ở cả nút trong khi số bước còn lại là chẵn.

Đề VOI

• Biến đổi bảng (voi06_change) (Chuyên gia) VOI 2006: bài nhánh cận thực thụ hiếm hoi của VOI; hãy tìm tính chất đơn điệu khiến nhiều nước đi luôn "an toàn" để chỉ rẽ nhánh khi buộc phải chọn, rồi kết hợp ghi nhớ trạng thái và một cận trên để dừng sớm.
• Phần thưởng (voi13_bonus) (Trung cấp) VOI 2013: vét cạn thuần túy hơn là quay lui có cắt tỉa; không gian cấu hình đủ nhỏ để duyệt hết, việc cần làm là tính thật nhanh giá trị của mỗi cấu hình.
• Chất lượng dịch vụ (voi14_qos) (Kỳ cựu) VOI 2014, chỉ dùng cho subtask $n\le 10$: quay lui liệt kê các đường theo thứ tự từ điển, cắt nhánh khi độ trễ đã đi cộng độ trễ nhỏ nhất còn lại tới đích (một cận dưới) đã vượt giới hạn; lời giải đầy đủ phải đếm số đường thay vì liệt kê từng đường.
• Tạo đề thi (voi16_exam) (Kỳ cựu) VOI 2016, chỉ dùng cho subtask 1: quay lui chọn một giá trị cho từng biểu thức sao cho các kết quả đôi một khác nhau; subtask lớn cần kỹ thuật khác vì xung đột có thể chỉ lộ ra ở cuối dữ liệu, làm số nhánh bùng nổ.
• SEQ198 (voi16_seq198) (Nâng cao) VOI 2016, chỉ dùng cho subtask $m\le 20$: quay lui chọn/không chọn từng giá trị, chỉ chọn khi không xung đột với các giá trị đã giữ; lời giải đầy đủ cần một kỹ thuật khác (xem DP bitmask).