Giới thiệu

Duyệt toàn bộ các khả năng là kỹ thuật nền tảng trong lập trình thuật toán. Hiểu rõ cách duyệt tuần tự, duyệt mọi cặp, bộ ba, tập con, hoán vị… giúp học sinh tự tin giải quyết các bài toán yêu cầu liệt kê, kiểm tra, hoặc tối ưu nghiệm trên tập nhỏ.

Bài viết này tổng hợp hướng dẫn từng kiểu duyệt, kèm ví dụ minh họa và bài tập tự luyện.

1. Duyệt tuần tự

Mô tả

• Duyệt lần lượt qua tất cả các phần tử trong một tập hợp (mảng, vector).

Ví dụ mẫu

for (int i = 0; i < n; ++i) {
    cout << a[i] << " ";
}

Bài tập tự luyện

• Printing Array: In ra lần lượt các phần tử mảng.
• Sum of Array: Tính tổng các phần tử mảng.
• Maximum Element: Tìm phần tử lớn nhất.
• Even Count: Đếm số phần tử chẵn.
• Odd Positions: In các phần tử ở vị trí lẻ.

Gợi ý: Dùng vòng for đơn để duyệt từ 0 đến n-1.

2. Duyệt mọi cặp (2 phần tử)

Mô tả

• Duyệt tất cả các cặp $(i, j)$ với $i < j$.

Ví dụ mẫu

for (int i = 0; i < n; ++i)
    for (int j = i+1; j < n; ++j)
        cout << a[i] << ", " << a[j] << endl;

Bài tập tự luyện

• Two Sum: Tìm hai số cộng lại được target.
• Good Pairs: Đếm số cặp bằng nhau.
• Minimum Absolute Difference: Tìm cặp có hiệu nhỏ nhất.
• Max Product of Two Elements: Tìm tích lớn nhất hai phần tử.
• Sum of Two Integers: Thử mọi cặp số nguyên.

Gợi ý: Duyệt hai vòng lồng nhau, chỉ xét $j>i$.

3. Duyệt mọi bộ ba (3 phần tử)

Mô tả

• Duyệt tất cả các bộ ba $(i, j, k)$ với $i < j < k$.

Ví dụ mẫu

for (int i = 0; i < n; ++i)
    for (int j = i+1; j < n; ++j)
        for (int k = j+1; k < n; ++k)
            cout << a[i] << ", " << a[j] << ", " << a[k] << endl;

Bài tập tự luyện

• 3Sum: Tìm bộ ba có tổng bằng 0.
• Triangle Count: Đếm số bộ ba tạo thành tam giác.
• Triplets with Smaller Sum: Bộ ba có tổng nhỏ hơn target.
• Closest 3Sum: Bộ ba tổng gần nhất target.
• Three Equal Parts: Chia mảng thành ba phần bằng nhau.

Gợi ý: Ba vòng for lồng nhau.

4. Duyệt mọi bộ 4, 5, 6 phần tử

• Duyệt tương tự bộ 2, bộ 3, thêm vòng lặp cho mỗi thành phần.
• Độ phức tạp tăng rất nhanh: $O(n^k)$ với bộ $k$ phần tử.
• Chỉ áp dụng khi $n$ nhỏ.

Bài tập tự luyện (Bộ 4)

• 4Sum: Tìm bộ bốn có tổng bằng target.
• Quadruplet Sum to Target: Tìm bộ bốn từ 4 mảng.
• Four Sum II: Đếm số bộ bốn tổng bằng 0.
• Rectangle Detection: Tìm hình chữ nhật nhỏ nhất.
• Maximize Number of Quadruplets: Chọn bộ bốn thỏa điều kiện.

Gợi ý: Duyệt 4 vòng for hoặc tối ưu bằng map.

5. Duyệt mọi tập con (Subset)

Mô tả

• Với tập $n$ phần tử, có $2^n$ tập con.

Ví dụ mẫu

for (int mask = 0; mask < (1 << n); ++mask) {
    for (int i = 0; i < n; ++i)
        if (mask >> i & 1)
            cout << a[i] << " ";
}

Bài tập tự luyện

• Subsets: Liệt kê tất cả tập con.
• Subset Sum: Có tồn tại tập con có tổng = target không?
• K Subsets with Equal Sum: Chia tập thành K tập con có tổng bằng nhau.
• Minimum Difference Subsets: Chia tập sao cho hiệu tổng hai phần nhỏ nhất.
• Count Subsets with Sum K: Đếm số tập con có tổng bằng k.

Gợi ý: Duyệt bằng bitmask, mỗi bit ứng với chọn/không chọn.

6. Duyệt mọi hoán vị (Permutation)

Mô tả

• Với tập $n$ phần tử, có $n!$ hoán vị.

Ví dụ mẫu

sort(a, a+n);
do {
    for (int i = 0; i < n; ++i) cout << a[i] << " ";
} while (next_permutation(a, a+n));

Bài tập tự luyện

• Permutations: Sinh ra tất cả hoán vị.
• Next Permutation: Tìm hoán vị kế tiếp.
• Permutations II: Sinh hoán vị không trùng lặp.
• Sequence Reconstruction: Kiểm tra khôi phục hoán vị ban đầu.
• Rearrange String k Distance Apart: Xếp chuỗi theo điều kiện khoảng cách.

Gợi ý: Dùng next_permutation hoặc đệ quy backtracking.

Kết luận

Hiểu và thành thạo các kỹ thuật duyệt toàn bộ sẽ giúp học sinh:

• Tự tin giải quyết các bài toán nhỏ.
• Làm nền tảng để học thuật toán tối ưu hơn (quy hoạch động, backtracking).
• Rèn luyện khả năng phân tích độ phức tạp.

Chúc bạn luyện tập vui vẻ và tiến bộ vững chắc! 🚀