↩️ Quay lui (Backtracking)

Hình dung bạn đi trong một mê cung: gặp ngã rẽ, bạn chọn một hướng và đi tiếp; nếu đường đó dẫn vào ngõ cụt, bạn quay lại đúng ngã rẽ đó và thử hướng còn lại. Backtracking (quay lui) áp dụng chính xác chiến lược này vào việc giải các bài toán mà lời giải được xây dựng dần dần qua nhiều lựa chọn: thử một lựa chọn, đệ quy đi tiếp với lựa chọn đó; nếu ngõ cụt (vi phạm điều kiện, hoặc đã xét hết vẫn không ra), hoàn tác (undo) lựa chọn vừa thử rồi quay lại thử lựa chọn khác.

Về bản chất, backtracking là một cách tổ chức việc duyệt vét cạn (brute force) không gian lời giải bằng đệ quy (một dạng DFS), nhưng có khả năng cắt tỉa (pruning): ngay khi phát hiện một nhánh lựa chọn chắc chắn không dẫn tới lời giải hợp lệ, ta dừng khám phá nhánh đó ngay lập tức thay vì đi hết rồi mới nhận ra sai - tiết kiệm rất nhiều thời gian so với vét cạn thuần túy.

Khung sườn chung

Hầu hết bài toán backtracking đều viết theo một khuôn mẫu ba bước: chọn (choose) → khám phá tiếp (explore) → bỏ chọn (unchoose).

def backtrack(state, choices, res):
    if is_solution(state):        # đủ điều kiện là 1 lời giải hoàn chỉnh
        res.append(state.copy())
        return
    for choice in choices:
        if not is_valid(state, choice):   # cắt tỉa: bỏ qua lựa chọn chắc chắn sai
            continue
        state.append(choice)              # CHỌN
        backtrack(state, choices, res)    # KHÁM PHÁ TIẾP (đệ quy)
        state.pop()                       # BỎ CHỌN - quay lui, khôi phục trạng thái

Dòng state.pop() chính là “bước quay lui”: sau khi nhánh đệ quy với lựa chọn đó đã được khám phá hết (dù thành công hay thất bại), ta gỡ lựa chọn ra khỏi trạng thái hiện tại để trạng thái sẵn sàng cho lần thử lựa chọn kế tiếp trong vòng for.

Ví dụ 1: Sinh hoán vị (Permutations)

Cho một danh sách n số phân biệt, liệt kê tất cả các cách sắp xếp (hoán vị) của chúng. Lựa chọn ở mỗi bước: “chọn số nào tiếp theo cho vị trí hiện tại, trong các số chưa dùng”.

def permute(nums):
    res = []
    path = []
    used = [False] * len(nums)

    def backtrack():
        if len(path) == len(nums):       # đã chọn đủ n số -> 1 hoán vị hoàn chỉnh
            res.append(path.copy())
            return
        for i, num in enumerate(nums):
            if used[i]:                   # cắt tỉa: số này đã dùng rồi
                continue
            path.append(num)
            used[i] = True
            backtrack()
            path.pop()                    # quay lui
            used[i] = False

    backtrack()
    return res

permute([1, 2, 3])
# [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

Mảng used chính là điều kiện cắt tỉa: không có nó, thuật toán sẽ thử chọn lại một số đã dùng, sinh ra kết quả sai (lặp phần tử).

Ví dụ 2: Tổng tập con (Subset Sum)

Cho một mảng số dương và một target, tìm tất cả các tập con có tổng đúng bằng target (mỗi phần tử được dùng tối đa 1 lần). Lựa chọn ở mỗi bước: “có lấy phần tử này vào tập con hay không”.

def subset_sum(nums, target):
    res = []
    path = []
    nums.sort()  # sắp xếp trước để cắt tỉa hiệu quả hơn

    def backtrack(start, remain):
        if remain == 0:
            res.append(path.copy())
            return
        for i in range(start, len(nums)):
            if nums[i] > remain:          # cắt tỉa: mảng đã sort, các số sau còn to hơn -> chắc chắn hỏng
                break
            path.append(nums[i])
            backtrack(i + 1, remain - nums[i])  # i+1: không quay lại chọn số đã dùng
            path.pop()

    backtrack(0, target)
    return res

subset_sum([2, 3, 5], 5)  # [[2,3],[5]]

Điều kiện if nums[i] > remain: break là một phép cắt tỉa quan trọng: vì mảng đã sắp xếp, một khi số hiện tại đã vượt quá phần còn thiếu, mọi số phía sau (đều lớn hơn hoặc bằng) cũng chắc chắn vượt quá - không cần thử tiếp, thoát vòng lặp ngay.

Ví dụ 3: N-Queens

Đặt n quân hậu lên bàn cờ n × n sao cho không quân nào ăn được quân nào (không cùng hàng, cùng cột, hoặc cùng đường chéo). Lựa chọn ở mỗi bước: “đặt quân hậu của hàng hiện tại vào cột nào”.

def solve_n_queens(n):
    res = []
    cols = set()       # các cột đã có hậu
    diag1 = set()       # đường chéo chính đã có hậu (hàng - cột không đổi)
    diag2 = set()       # đường chéo phụ đã có hậu (hàng + cột không đổi)
    path = []            # path[r] = cột đặt hậu ở hàng r

    def backtrack(row):
        if row == n:
            res.append(path.copy())
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue  # cắt tỉa: vị trí này chắc chắn bị ăn
            path.append(col)
            cols.add(col); diag1.add(row - col); diag2.add(row + col)
            backtrack(row + 1)
            path.pop()                                  # quay lui
            cols.remove(col); diag1.remove(row - col); diag2.remove(row + col)

    backtrack(0)
    return res

Ba tập hợp cols, diag1, diag2 cho phép kiểm tra một vị trí có “an toàn” hay không trong O(1), thay vì phải quét lại toàn bộ các quân hậu đã đặt - đây là kỹ thuật cắt tỉa cốt lõi khiến N-Queens chạy được với n tương đối lớn dù bản chất vẫn là vét cạn.

Vì sao cắt tỉa quan trọng đến vậy?

Không cắt tỉa, không gian lựa chọn của các bài toán trên tăng theo cấp giai thừa hoặc mũ (permutation của n phần tử là n! khả năng, N-Queens vét cạn thô là n^n). Cắt tỉa không đổi bậc độ phức tạp trong trường hợp xấu nhất, nhưng trong thực tế nó loại bỏ phần lớn nhánh vô nghĩa rất sớm, khiến bài toán từ “không thể chạy nổi với n = 20” trở thành “chạy được trong vài giây”.

Tóm tắt

Backtracking = đệ quy (DFS) + hoàn tác lựa chọn khi ngõ cụt, theo khuôn mẫu chọn - khám phá tiếp - bỏ chọn.
Cắt tỉa (pruning): bỏ qua sớm những nhánh chắc chắn không dẫn tới lời giải hợp lệ, không đổi bậc worst-case nhưng cải thiện mạnh trong thực tế.
Dùng khi cần liệt kê/đếm mọi lời giải thỏa điều kiện (hoán vị, tổ hợp, N-Queens…), khác với DP là dùng khi có bài toán con chồng lặp cần ghi nhớ.