Bài 12.1. Nguyên lý quay lui và thiết kế thuật toán

Chào mừng bạn trở lại với hành trình khám phá thế giới Cấu trúc dữ liệu và Giải thuật! Hôm nay, chúng ta sẽ cùng nhau bước vào một khu vực đầy thử thách nhưng cũng vô cùng thú vị của thiết kế thuật toán: Nguyên lý Quay lui (Backtracking).

Bạn đã bao giờ cảm thấy như đang lạc trong một mê cung, thử một con đường, nhận ra nó không đi đến đâu, rồi quay trở lại điểm rẽ cuối cùng để thử một hướng khác chưa? Đó chính là linh hồn của nguyên lý quay lui!

Nguyên lý quay lui là một kỹ thuật giải thuật tổng quát dùng để tìm kiếm lời giải cho các bài toán mang tính tổ hợp, nơi chúng ta cần xây dựng một giải pháp từng bước một. Nếu tại một bước nào đó, chúng ta nhận thấy rằng việc tiếp tục theo hướng hiện tại sẽ không thể dẫn đến một giải pháp hợp lệ (dựa trên các ràng buộc của bài toán), chúng ta sẽ "quay lui" (backtrack) về bước trước đó và thử một lựa chọn khác.

Hãy hình dung không gian tìm kiếm của bài toán như một cái cây khổng lồ, gọi là Cây không gian trạng thái (State Space Tree). Mỗi nút trên cây biểu diễn một trạng thái hay một giải pháp bộ phận (partial solution). Các cạnh từ một nút biểu diễn các lựa chọn (choices) có thể có để chuyển từ trạng thái hiện tại sang trạng thái tiếp theo, xây dựng thêm cho giải pháp bộ phận. Thuật toán quay lui duyệt cái cây này theo kiểu tìm kiếm theo chiều sâu (DFS).

Điểm đặc biệt và sức mạnh của quay lui nằm ở kỹ thuật "cắt tỉa" (pruning). Nếu tại một nút nào đó, chúng ta có thể xác định rằng không có con đường nào từ nút này trở đi có thể dẫn đến một giải pháp cuối cùng hợp lệ, chúng ta sẽ cắt bỏ toàn bộ nhánh cây đó và không cần phải khám phá sâu hơn nữa. Điều này giúp giảm đáng kể không gian tìm kiếm so với việc duyệt mù quáng mọi khả năng.

Hầu hết các thuật toán quay lui được cài đặt một cách tự nhiên bằng phương pháp đệ quy. Hàm đệ quy thường nhận vào trạng thái hiện tại của giải pháp bộ phận và thực hiện các bước sau:

Kiểm tra xem giải pháp bộ phận hiện tại đã là một giải pháp cuối cùng hợp lệ chưa (đây là điều kiện dừng/trường hợp cơ sở). Nếu có, ghi nhận giải pháp và có thể dừng lại hoặc tiếp tục tìm kiếm các giải pháp khác.
Nếu chưa phải giải pháp cuối cùng, liệt kê tất cả các lựa chọn có thể có từ trạng thái hiện tại.
Với mỗi lựa chọn:
- Áp dụng lựa chọn đó, chuyển sang một trạng thái mới (xây dựng thêm cho giải pháp bộ phận).
- Gọi đệ quy với trạng thái mới này để tiếp tục xây dựng giải pháp.
- Hoàn tác lựa chọn vừa áp dụng (đây chính là bước quay lui). Điều này là cực kỳ quan trọng để thử các lựa chọn khác từ trạng thái trước đó.

Thiết kế thuật toán quay lui: Công thức chung

Để thiết kế một thuật toán quay lui, bạn cần xác định rõ các yếu tố sau:

Trạng thái (State): Định nghĩa rõ ràng những gì cần lưu trữ để biểu diễn một giải pháp bộ phận tại một bước bất kỳ trong quá trình xây dựng.
Lựa chọn (Choices): Tại một trạng thái cho trước, có những hành động hoặc quyết định nào có thể thực hiện để mở rộng giải pháp bộ phận?
Ràng buộc (Constraints): Những điều kiện nào phải được thỏa mãn để một giải pháp bộ phận được coi là có tiềm năng dẫn đến giải pháp cuối cùng? Đây là cơ sở để thực hiện "cắt tỉa".
Mục tiêu/Điều kiện dừng (Goal/Base Case): Khi nào thì giải pháp bộ phận hiện tại được coi là một giải pháp hợp lệ cho bài toán?

Ví dụ minh họa 1: Bài toán Sinh Hoán vị (Permutations)

Hãy bắt đầu với một bài toán kinh điển: cho một tập hợp các phần tử phân biệt, hãy liệt kê tất cả các hoán vị có thể có của tập hợp đó.

Ví dụ: Với tập {1, 2, 3}, các hoán vị là {1, 2, 3}, {1, 3, 2}, {2, 1, 3}, {2, 3, 1}, {3, 1, 2}, {3, 2, 1}.

Trạng thái: Một hoán vị bộ phận đang được xây dựng (ví dụ: {1, 3, _}).
Lựa chọn: Tại mỗi bước, chúng ta có thể chọn một trong các phần tử chưa được sử dụng từ tập ban đầu để thêm vào vị trí tiếp theo trong hoán vị bộ phận.
Ràng buộc: Mỗi phần tử chỉ được sử dụng một lần trong một hoán vị.
Mục tiêu: Hoán vị bộ phận có độ dài bằng với số lượng phần tử ban đầu.

Chúng ta có thể cài đặt bằng đệ quy, truyền vào chỉ số vị trí hiện tại đang muốn điền vào hoán vị.

#include <iostream>
#include <vector>
#include <algorithm>

void generatePermutationsUtil(
    const std::vector<int>& original_array, // Tập hợp ban đầu
    std::vector<int>& current_permutation, // Hoán vị đang xây dựng (giải pháp bộ phận)
    std::vector<bool>& used, // Mảng theo dõi các phần tử đã dùng
    std::vector<std::vector<int>>& results // Nơi lưu trữ các hoán vị cuối cùng
) {
    // 1. Mục tiêu/Điều kiện dừng:
    // Nếu hoán vị hiện tại đã có độ dài bằng với tập ban đầu
    if (current_permutation.size() == original_array.size()) {
        // Đã tìm thấy một hoán vị hoàn chỉnh, lưu lại
        results.push_back(current_permutation);
        return; // Quay lui về bước trước để thử các lựa chọn khác
    }

    // 2. Lựa chọn:
    // Duyệt qua tất cả các phần tử trong tập ban đầu
    for (int i = 0; i < original_array.size(); ++i) {
        // 3. Ràng buộc:
        // Kiểm tra xem phần tử original_array[i] đã được sử dụng trong hoán vị hiện tại chưa
        if (!used[i]) {
            // Nếu chưa được sử dụng:

            // **Áp dụng lựa chọn:**
            // Đánh dấu phần tử này đã được sử dụng
            used[i] = true;
            // Thêm phần tử này vào cuối hoán vị đang xây dựng
            current_permutation.push_back(original_array[i]);

            // **Gọi đệ quy:**
            // Tiếp tục xây dựng hoán vị cho vị trí tiếp theo
            generatePermutationsUtil(original_array, current_permutation, used, results);

            // **Quay lui (Hoàn tác lựa chọn):**
            // Xóa phần tử vừa thêm vào (để thử các phần tử khác cho vị trí hiện tại)
            current_permutation.pop_back();
            // Đánh dấu phần tử này là chưa được sử dụng lại (để nó có thể được dùng ở các nhánh khác của cây)
            used[i] = false;
        }
    }
}

std::vector<std::vector<int>> generatePermutations(const std::vector<int>& nums) {
    std::vector<std::vector<int>> results;
    if (nums.empty()) {
        return results; // Không có phần tử, không có hoán vị
    }

    std::vector<int> current_permutation;
    std::vector<bool> used(nums.size(), false); // Ban đầu, không có phần tử nào được sử dụng

    generatePermutationsUtil(nums, current_permutation, used, results);

    return results;
}

int main() {
    std::vector<int> nums = {1, 2, 3};
    std::vector<std::vector<int>> permutations = generatePermutations(nums);

    std::cout << "Cac hoan vi cua {1, 2, 3} la:" << std::endl;
    for (const auto& p : permutations) {
        std::cout << "[ ";
        for (int i = 0; i < p.size(); ++i) {
            std::cout << p[i] << (i == p.size() - 1 ? "" : ", ");
        }
        std::cout << " ]" << std::endl;
    }

    std::vector<int> nums2 = {5, 6};
     std::vector<std::vector<int>> permutations2 = generatePermutations(nums2);

    std::cout << "\nCac hoan vi cua {5, 6} la:" << std::endl;
    for (const auto& p : permutations2) {
        std::cout << "[ ";
        for (int i = 0; i < p.size(); ++i) {
            std::cout << p[i] << (i == p.size() - 1 ? "" : ", ");
        }
        std::cout << " ]" << std::endl;
    }


    return 0;
}

Giải thích code:

Hàm chính generatePermutations nhận vector đầu vào và trả về vector chứa tất cả các hoán vị. Nó khởi tạo vector current_permutation rỗng (để xây dựng giải pháp bộ phận), mảng used (để theo dõi phần tử nào đã dùng) và vector results (để lưu kết quả cuối cùng). Sau đó, nó gọi hàm đệ quy generatePermutationsUtil.
Hàm đệ quy generatePermutationsUtil:
- original_array: Tập gốc, không đổi.
- current_permutation: Hoán vị đang được xây dựng. Chúng ta truyền tham chiếu để có thể sửa đổi nó trong các lời gọi đệ quy sâu hơn.
- used: Mảng boolean theo dõi các phần tử đã được chọn vào current_permutation. Cũng truyền tham chiếu.
- results: Vector lưu trữ kết quả cuối cùng. Truyền tham chiếu.
- Điều kiện dừng: Nếu kích thước của current_permutation bằng kích thước của original_array, tức là chúng ta đã điền đủ các vị trí, một hoán vị hoàn chỉnh đã được tạo ra. Ta thêm nó vào results và return để quay lui.
- Vòng lặp lựa chọn: Duyệt qua tất cả các phần tử trong original_array (từ i = 0 đến size-1).
- Kiểm tra ràng buộc: Dùng used[i] để xem phần tử ở chỉ số i đã được chọn chưa. Nếu !used[i] (chưa dùng), chúng ta xem xét nó như một lựa chọn khả thi cho vị trí hiện tại.
- Áp dụng lựa chọn: Nếu phần tử original_array[i] chưa dùng, ta đánh dấu used[i] = true và thêm nó vào cuối current_permutation bằng push_back().
- Gọi đệ quy: Sau khi áp dụng lựa chọn, ta gọi đệ quy generatePermutationsUtil để tiếp tục quá trình xây dựng cho các vị trí còn lại của hoán vị.
- Quay lui: Đây là bước quan trọng nhất của backtracking. Sau khi lời gọi đệ quy kết thúc (dù nó tìm thấy giải pháp hay bị "cắt tỉa" và quay về), chúng ta cần hoàn tác lựa chọn vừa rồi để có thể thử các lựa chọn khác từ trạng thái hiện tại. Ta xóa phần tử vừa thêm vào current_permutation bằng pop_back() và đánh dấu lại used[i] = false. Bước này cho phép các nhánh khác của cây không gian trạng thái được khám phá.

Ví dụ minh họa 2: Bài toán N Quân Hậu (N-Queens Problem)

Một bài toán cổ điển khác rất phù hợp để minh họa backtracking là bài toán N Quân Hậu. Đề bài: đặt N quân hậu trên bàn cờ N×N sao cho không có hai quân hậu nào tấn công lẫn nhau (tức là không có hai quân hậu nào cùng nằm trên một hàng, một cột, hoặc một đường chéo). Tìm tất cả các cách đặt quân hậu thỏa mãn.

Ví dụ: Với N=4, có 2 cách đặt quân hậu.

Trạng thái: Việc đặt các quân hậu vào các cột từ 0 đến k-1. Ta có thể biểu diễn trạng thái bằng một mảng board[N], trong đó board[c] = r nghĩa là quân hậu ở cột c được đặt ở hàng r.
Lựa chọn: Tại cột hiện tại col, chúng ta có thể thử đặt quân hậu vào bất kỳ hàng nào từ 0 đến N-1.
Ràng buộc: Việc đặt quân hậu ở hàng row tại cột col phải không xung đột với các quân hậu đã đặt ở các cột trước đó (0 đến col-1). Xung đột xảy ra nếu có quân hậu khác cùng hàng, cùng cột, hoặc cùng đường chéo.
- Cùng hàng: board[prev_col] == row (kiểm tra với mọi prev_col < col).
- Cùng cột: Đã được đảm bảo vì chúng ta đặt quân hậu lần lượt từng cột.
- Cùng đường chéo: Hai vị trí (r1, c1) và (r2, c2) cùng đường chéo nếu r1 - c1 == r2 - c2 (đường chéo từ trên trái xuống dưới phải) hoặc r1 + c1 == r2 + c2 (đường chéo từ trên phải xuống dưới trái).

Để kiểm tra ràng buộc hiệu quả, thay vì duyệt lại tất cả các quân hậu đã đặt, chúng ta có thể dùng các mảng boolean để theo dõi các hàng và đường chéo đã bị chiếm đóng:

row_attacked[row]: true nếu hàng row đã bị chiếm.
diag1_attacked[row + col]: true nếu đường chéo row + col đã bị chiếm (tổng tọa độ không đổi trên đường chéo này).
diag2_attacked[row - col + N - 1]: true nếu đường chéo row - col đã bị chiếm (hiệu tọa độ không đổi trên đường chéo này). Ta cộng thêm N-1 để đảm bảo chỉ số không âm và nằm trong khoảng [0, 2N-2].
Mục tiêu: Đã đặt thành công quân hậu vào tất cả N cột (tức là col == N).

#include <iostream>
#include <vector>
#include <string>

// Hàm in ra cấu hình bàn cờ
void printBoard(const std::vector<std::string>& board) {
    for (const auto& row : board) {
        std::cout << row << std::endl;
    }
    std::cout << std::endl;
}

// Hàm đệ quy quay lui để giải bài toán N Queens
void solveNQueensUtil(
    int col, // Cột hiện tại đang xét
    int n, // Kích thước bàn cờ N
    std::vector<std::string>& current_board, // Cấu hình bàn cờ hiện tại đang xây dựng
    std::vector<bool>& row_attacked, // Mảng đánh dấu các hàng đã bị tấn công
    std::vector<bool>& diag1_attacked, // Mảng đánh dấu các đường chéo (r+c) đã bị tấn công
    std::vector<bool>& diag2_attacked, // Mảng đánh dấu các đường chéo (r-c) đã bị tấn công
    std::vector<std::vector<std::string>>& results // Nơi lưu trữ các cấu hình giải pháp cuối cùng
) {
    // 1. Mục tiêu/Điều kiện dừng:
    // Nếu đã đặt được quân hậu vào tất cả N cột (tức là col == N)
    if (col == n) {
        // Đã tìm thấy một giải pháp hoàn chỉnh, lưu lại
        results.push_back(current_board);
        return; // Quay lui về cột trước để thử các lựa chọn khác
    }

    // 2. Lựa chọn:
    // Thử đặt quân hậu vào từng hàng 'row' của cột hiện tại 'col'
    for (int row = 0; row < n; ++row) {
        // 3. Ràng buộc:
        // Kiểm tra xem vị trí (row, col) có an toàn để đặt quân hậu không
        // (không bị tấn công bởi các quân hậu đã đặt ở các cột trước đó)
        if (!row_attacked[row] && !diag1_attacked[row + col] && !diag2_attacked[row - col + n - 1]) {
            // Nếu vị trí an toàn:

            // **Áp dụng lựa chọn:**
            // Đánh dấu hàng và các đường chéo tương ứng đã bị tấn công
            row_attacked[row] = true;
            diag1_attacked[row + col] = true;
            diag2_attacked[row - col + n - 1] = true;
            // Đặt quân hậu vào vị trí (row, col) trên bàn cờ hiện tại
            current_board[row][col] = 'Q';

            // **Gọi đệ quy:**
            // Tiếp tục quá trình đặt quân hậu cho cột tiếp theo (col + 1)
            solveNQueensUtil(col + 1, n, current_board, row_attacked, diag1_attacked, diag2_attacked, results);

            // **Quay lui (Hoàn tác lựa chọn):**
            // Xóa quân hậu khỏi vị trí (row, col)
            current_board[row][col] = '.';
            // Hoàn tác việc đánh dấu hàng và các đường chéo
            row_attacked[row] = false;
            diag1_attacked[row + col] = false;
            diag2_attacked[row - col + n - 1] = false;
        }
    }
}

std::vector<std::vector<std::string>> solveNQueens(int n) {
    std::vector<std::vector<std::string>> results;
    if (n <= 0) {
        return results; // N không hợp lệ
    }

    // Khởi tạo bàn cờ rỗng
    std::vector<std::string> current_board(n, std::string(n, '.'));

    // Khởi tạo các mảng theo dõi trạng thái tấn công
    std::vector<bool> row_attacked(n, false);
    std::vector<bool> diag1_attacked(2 * n - 1, false); // r + c có giá trị từ 0 đến 2n-2
    std::vector<bool> diag2_attacked(2 * n - 1, false); // r - c + n - 1 có giá trị từ 0 đến 2n-2

    // Bắt đầu quá trình đặt quân hậu từ cột 0
    solveNQueensUtil(0, n, current_board, row_attacked, diag1_attacked, diag2_attacked, results);

    return results;
}

int main() {
    int n = 4;
    std::vector<std::vector<std::string>> solutions = solveNQueens(n);

    std::cout << "Tim thay " << solutions.size() << " giai phap cho bai toan " << n << " Quan Hau:" << std::endl;
    for (const auto& sol : solutions) {
        printBoard(sol);
    }

     int n2 = 8;
    std::vector<std::vector<std::string>> solutions2 = solveNQueens(n2);
    std::cout << "Tim thay " << solutions2.size() << " giai phap cho bai toan " << n2 << " Quan Hau:" << std::endl;
    // Không in bàn cờ cho N=8 vì quá dài, chỉ in số lượng giải pháp.

    return 0;
}

Giải thích code:

Hàm chính solveNQueens nhận kích thước bàn cờ n, khởi tạo các cấu trúc dữ liệu cần thiết: current_board (vector of string biểu diễn bàn cờ, '.' là ô trống, 'Q' là quân hậu), row_attacked, diag1_attacked, diag2_attacked (các mảng boolean để kiểm tra ràng buộc nhanh chóng), và results để lưu các giải pháp hoàn chỉnh. Sau đó, nó gọi hàm đệ quy solveNQueensUtil bắt đầu từ cột 0.
Hàm đệ quy solveNQueensUtil:
- col: Cột hiện tại đang xem xét để đặt quân hậu.
- n: Kích thước bàn cờ.
- current_board, row_attacked, diag1_attacked, diag2_attacked, results: Các tham số được truyền tham chiếu để có thể sửa đổi và ghi nhận kết quả.
- Điều kiện dừng: Nếu col == n, nghĩa là chúng ta đã đặt thành công quân hậu vào N cột (từ 0 đến N-1). Cấu hình current_board hiện tại là một giải pháp hợp lệ. Ta thêm nó vào results và return.
- Vòng lặp lựa chọn: Duyệt qua tất cả các hàng row từ 0 đến n-1 trong cột hiện tại col. Mỗi hàng là một vị trí tiềm năng để đặt quân hậu.
- Kiểm tra ràng buộc: Sử dụng các mảng row_attacked, diag1_attacked, diag2_attacked để kiểm tra xem vị trí (row, col) có bị tấn công bởi các quân hậu đã đặt ở các cột 0 đến col-1 hay không. Nếu không bị tấn công, vị trí này là an toàn.
- Áp dụng lựa chọn: Nếu an toàn, ta đánh dấu các hàng và đường chéo tương ứng là đã bị tấn công (true). Sau đó, đặt quân hậu vào vị trí (row, col) trên current_board bằng cách thay ký tự '.' thành 'Q'.
- Gọi đệ quy: Sau khi áp dụng lựa chọn, ta gọi đệ quy solveNQueensUtil(col + 1, ...) để tiếp tục quá trình đặt quân hậu cho cột tiếp theo.
- Quay lui: Đây là bước mấu chốt. Sau khi lời gọi đệ quy kết thúc, ta cần hoàn tác việc đặt quân hậu ở vị trí (row, col) để có thể thử đặt quân hậu ở các hàng khác trong cùng cột col. Ta xóa quân hậu (current_board[row][col] = '.') và hoàn tác việc đánh dấu trên các mảng attacked thành false. Bước này cho phép thuật toán "quay trở lại" và khám phá các khả năng khác ở cột col.

Ưu điểm và Nhược điểm của Nguyên lý Quay lui

Ưu điểm:

Tính tổng quát: Có thể áp dụng cho một phạm vi rộng các bài toán tìm kiếm giải pháp trong không gian tổ hợp.
Đảm bảo tìm thấy giải pháp: Nếu tồn tại ít nhất một giải pháp, thuật toán quay lui (nếu được triển khai đúng) sẽ tìm thấy nó (và có thể tìm thấy tất cả các giải pháp).
Tính linh hoạt: Dễ dàng thêm các ràng buộc mới để cải thiện hiệu quả bằng cách cắt tỉa nhiều hơn.

Nhược điểm:

Hiệu suất: Trong trường hợp xấu nhất, quay lui có thể phải khám phá một phần lớn (hoặc toàn bộ) không gian trạng thái, dẫn đến độ phức tạp thời gian theo cấp số mũ (exponential), khiến nó không khả thi cho các bài toán có kích thước lớn.
Bộ nhớ: Việc sử dụng đệ quy có thể dẫn đến việc sử dụng bộ nhớ đáng kể cho stack call (ngăn xếp lời gọi).

Khi nào nên sử dụng Nguyên lý Quay lui?

Quay lui là một lựa chọn tốt khi bạn gặp các bài toán có cấu trúc sau:

Cần xây dựng một giải pháp bằng cách thực hiện một chuỗi các quyết định (lựa chọn).
Có các ràng buộc rõ ràng cho phép kiểm tra tính hợp lệ của một giải pháp bộ phận tại các bước trung gian.
Bạn cần tìm tất cả các giải pháp hoặc một giải pháp bất kỳ.
Kích thước bài toán đủ nhỏ để không gian trạng thái không bùng nổ quá mức.

Các bài toán phổ biến sử dụng quay lui bao gồm: Sudoku Solver, Graph Coloring (Tô màu đồ thị), Subset Sum (Tổng tập con), Knight's Tour (Đường đi của quân Mã), các bài toán về logic và constraint satisfaction...

Bài tập ví dụ:

[DSA-QuayLui-NhanhCan].Tập hợp có tổng bằng S.

Xét tất cả các tập hợp các số nguyên dương có các phần tử khác nhau và không lớn hơn số n cho trước. Nhiệm vụ của bạn là hãy đếm xem có tất cả bao nhiêu tập hợp có số lượng phần tử bằng k và tổng của tất cả các phần tử trong tập hợp bằng s? Các tập hợp là hoán vị của nhau chỉ được tính là một. Ví dụ với n = 9, k = 3, s = 23, là tập hợp duy nhất thỏa mãn.

Input Format

Gồm nhiều bộ test (không quá 100 test). Mỗi bộ test gồm 3 số nguyên n, k, s với 1 ≤ n ≤ 20, 1 ≤ k ≤ 10 và 1 ≤ s ≤ 155. Input kết thúc bởi 3 số 0.

Constraints

Output Format

Với mỗi test in ra số lượng các tập hợp thỏa mãn điều kiện đề bài.

Ví dụ:

Dữ liệu vào

Dữ liệu ra

Okay, đây là hướng dẫn giải bài toán "Tập hợp có tổng bằng S" sử dụng kỹ thuật quay lui kết hợp nhánh cận trong C++.

Bài toán yêu cầu đếm số lượng tập con (không xét thứ tự các phần tử) gồm k phần tử khác nhau, lấy từ tập {1, 2, ..., n}, sao cho tổng các phần tử trong tập con đó bằng s.

Với các ràng buộc n ≤ 20, k ≤ 10, s ≤ 155, ta có thể thấy không gian tìm kiếm không quá lớn cho các tập con kích thước k. Kỹ thuật quay lui (backtracking) là phù hợp. Để cải thiện hiệu suất, ta áp dụng thêm nhánh cận (branch and bound).

1. Ý tưởng Quay lui (Backtracking):

Ta sẽ xây dựng các tập con bằng cách chọn từng phần tử một từ tập {1, 2, ..., n}.
Để đảm bảo các phần tử khác nhau và tập con không bị lặp do thứ tự chọn, ta sẽ luôn chọn các phần tử theo thứ tự tăng dần. Tức là, nếu ta vừa chọn số x, thì số tiếp theo được chọn (nếu có) phải lớn hơn x.
Hàm đệ quy sẽ cần theo dõi các thông tin sau (trạng thái):
- Số hiện tại đang xét để chọn (hoặc bỏ qua).
- Số lượng phần tử đã chọn cho tập con hiện tại.
- Tổng của các phần tử đã chọn.

2. Thiết kế Hàm Đệ quy:

Gọi hàm đệ quy là solve(so_bat_dau, so_phan_tu_da_chon, tong_hien_tai).

so_bat_dau: Số nhỏ nhất có thể chọn trong bước này. Để đảm bảo thứ tự tăng dần, lần gọi đệ quy tiếp theo sẽ bắt đầu từ so_bat_dau + 1.
so_phan_tu_da_chon: Số lượng phần tử đã đưa vào tập con đang xây dựng.
tong_hien_tai: Tổng của các phần tử đã đưa vào tập con.

Hàm cần một biến toàn cục count_valid_subsets để đếm số lượng tập con hợp lệ tìm được.

3. Trường hợp Cơ sở (Base Case):

Nếu so_phan_tu_da_chon == k: Ta đã chọn đủ k phần tử. Kiểm tra xem tong_hien_tai có bằng s không. Nếu có, tăng count_valid_subsets lên 1. Dù tổng có bằng s hay không, nhánh tìm kiếm này kết thúc vì đã đủ số phần tử.

4. Bước Đệ quy:

Tại mỗi bước solve(so_bat_dau, so_phan_tu_da_chon, tong_hien_tai):

Ta sẽ thử chọn các số i từ so_bat_dau đến n làm phần tử tiếp theo của tập con.
Với mỗi số i được chọn:
- Gọi đệ quy solve(i + 1, so_phan_tu_da_chon + 1, tong_hien_tai + i). i + 1 đảm bảo phần tử tiếp theo lớn hơn i.

Vòng lặp thử các giá trị cho i từ so_bat_dau đến n sẽ bao hàm cả việc "bỏ qua" các số nhỏ hơn i trong bước hiện tại, vì ta chỉ bắt đầu xét từ so_bat_dau.

5. Nhánh cận (Pruning):

Để giảm bớt không gian tìm kiếm, ta dừng sớm các nhánh chắc chắn không dẫn đến kết quả:

Cận trên tổng: Nếu tong_hien_tai > s, không thể thêm số dương nào nữa mà tổng lại giảm về s. Dừng nhánh này. (Có thể kiểm tra tong_hien_tai + i > s trước khi gọi đệ quy để hiệu quả hơn).
Cận trên số lượng: Nếu so_phan_tu_da_chon > k, dừng nhánh này (thường được xử lý bởi trường hợp cơ sở).
Cận dưới số lượng còn lại: Nếu số lượng phần tử cần chọn thêm (k - so_phan_tu_da_chon) lớn hơn số lượng phần tử có thể chọn thêm từ so_bat_dau đến n (n - so_bat_dau + 1), thì không thể đạt được k phần tử. Dừng nhánh này.
Cận dưới tổng nhỏ nhất có thể: Nếu tong_hien_tai cộng với tổng của k - so_phan_tu_da_chon số nhỏ nhất có thể chọn tiếp theo (bắt đầu từ so_bat_dau) mà vẫn lớn hơn s, thì bất kỳ cách chọn nào khác từ đây cũng sẽ cho tổng lớn hơn s. Dừng nhánh này. Các số nhỏ nhất có thể chọn tiếp là so_bat_dau, so_bat_dau + 1, ..., so_bat_dau + (k - so_phan_tu_chon) - 1. Tổng của dãy số học này có thể tính nhanh.

6. Tối ưu giới hạn vòng lặp:

Trong bước đệ quy, khi chọn số i hiện tại, ta cần k - so_phan_tu_da_chon - 1 phần tử nữa sau i. Các phần tử này phải lấy từ i + 1 đến n. Số nhỏ nhất mà ta có thể chọn sau i là i+1. Để có đủ k - so_phan_tu_da_chon - 1 phần tử, số lớn nhất trong số đó, tức i + (k - so_phan_tu_da_chon - 1), phải không vượt quá n. Do đó, i + k - so_phan_tu_da_chon - 1 <= n Suy ra, i <= n - (k - so_phan_tu_da_chon - 1) = n - k + so_phan_tu_da_chon + 1. Đây chính là cận trên hiệu quả cho biến lặp i trong bước đệ quy, thay vì lặp tới tận n.

7. Hàm Main:

Đọc n, k, s trong vòng lặp.
Nếu n == 0 && k == 0 && s == 0 thì kết thúc.
Trước mỗi bộ test, reset count_valid_subsets = 0.
Gọi hàm đệ quy solve(1, 0, 0) để bắt đầu tìm kiếm (bắt đầu xét từ số 1, chưa chọn phần tử nào, tổng hiện tại là 0).
In ra giá trị của count_valid_subsets.

Tóm tắt cấu trúc hàm solve (ý tưởng):

void solve(int start_num, int count, int current_sum) {
    // Pruning: Tong hien tai vuot qua S
    if (current_sum > S) return; // Hoac check truoc khi cong i trong loop

    // Base case: Da du K phan tu
    if (count == K) {
        if (current_sum == S) count_valid_subsets++;
        return;
    }

    // Pruning: Khong du phan tu con lai de dat K
    // so phan tu can them = K - count
    // so phan tu con lai tu start_num den N = N - start_num + 1
    if (K - count > N - start_num + 1) return;

    // Pruning: Tong nho nhat co the dat duoc tu day da vuot qua S
    // Tong K-count so nho nhat tu start_num: start_num + (start_num+1) + ... + (start_num + K - count - 1)
    // long long min_sum_needed = ...;
    // if (current_sum + min_sum_needed > S) return;

    // Tinh gioi han tren cho vong lap i (so hien tai dang xet de them)
    // Sau khi them i, can K - count - 1 phan tu nua tu i+1 den N
    // Max i = N - (K - count - 1)
    int max_i = N - K + count + 1;

    // Duyet qua cac so co the chon lam phan tu tiep theo
    for (int i = start_num; i <= max_i; ++i) {
         // Pruning: Neu them i lam tong vuot qua S
         if (current_sum + i > S) {
             break; // Cac so lon hon i cung se lam tong vuot S
         }
        // Chon i va goi de quy
        solve(i + 1, count + 1, current_sum + i);
    }
}

Lưu ý sử dụng kiểu dữ liệu long long khi tính tổng để tránh tràn số trong các phép tính trung gian của nhánh cận, mặc dù tổng cuối cùng S và n không lớn lắm, nhưng các phép tính như (K-count) * (2*start_num + K - count - 1) có thể vượt quá giới hạn int.

Làm thêm nhiều bài tập miễn phí tại đây

Comments

There are no comments at the moment.