Trong lập trình, đặc biệt là trong lĩnh vực thuật toán và cấu trúc dữ liệu, ba thuật ngữ tập con (subset), dãy con (subsequence) và dãy con liên tiếp (contiguous subarray) xuất hiện thường xuyên và có ý nghĩa quan trọng trong việc giải quyết nhiều bài toán tối ưu, tìm kiếm và phân tích dữ liệu.
Tập con là khái niệm liên quan đến việc chọn một tập hợp các phần tử bất kỳ từ một mảng hoặc tập hợp ban đầu, không quan trọng thứ tự hay vị trí, nên thường được dùng trong các bài toán liệt kê tổ hợp, chia nhóm, hoặc balo nhị phân, nơi cần xét đến mọi khả năng chọn lựa phần tử. Các bài toán kinh điển như: ….
Dãy con, ngược lại, yêu cầu các phần tử được chọn phải giữ nguyên thứ tự xuất hiện trong mảng ban đầu, nhưng không nhất thiết phải liên tiếp. Đây là khái niệm trung gian giữa tập con và dãy con liên tiếp, và thường được sử dụng trong các bài toán như dãy con chung dài nhất (LCS), so khớp chuỗi, hay kiểm tra tính hợp lệ của một chuỗi theo quy tắc nào đó. Các bài toán kinh điển như: ….
Dãy con liên tiếp là một trường hợp đặc biệt của dãy con, trong đó các phần tử bắt buộc phải nằm liền kề nhau. Điều này giúp giảm số lượng trường hợp cần xét, và đặc biệt hữu ích trong các bài toán như tìm tổng lớn nhất (Kadane’s algorithm), tối ưu hóa đoạn con, hay phân tích chuỗi thời gian, nơi mà tính liên tục của dữ liệu mang ý nghĩa quan trọng. Các bài toán kinh điển như: ….
Hiểu rõ sự khác biệt giữa ba khái niệm này giúp lập trình viên lựa chọn chiến lược giải quyết phù hợp, tối ưu hoá thời gian và bộ nhớ trong các bài toán xử lý dữ liệu phức tạp.
| Tính chất | Tập con -Subset- | Dãy con -Subsequence- | Dãy con liên tiếp -Contiguous Subarray- |
|---|---|---|---|
| Chọn phần tử | Tùy ý | Tùy ý | Tùy ý |
| Giữ thứ tự gốc | ❌ Không cần | ✅ Bắt buộc giữ thứ tự | ✅ Bắt buộc giữ thứ tự |
| Các phần tử liền nhau | ❌ Không yêu cầu | ❌ Không yêu cầu | ✅ Bắt buộc liền nhau |
| Số lượng tối đa (với n phần tử) | {\ 2^{10} = 1024 \} | {\ 2^{10} = 1024 \} | \{ \frac{10(10+1)}{2} = 55 \} |
| Có thể rỗng không? | ✅ Có | ✅ Có | ✅ Có |
Ví dụ với [1,6,2,3,8,7,2,9,20,89] | [1, 3, 9, 89] (tự chọn, không quan trọng vị trí) | [1, 2, 8, 2, 89] (giữ thứ tự, bỏ qua một số phần tử) | [3, 8, 7, 2] (các phần tử liên tục trong mảng gốc) |
| Ứng dụng tiêu biểu | Sinh tổ hợp, bài toán balo | Dãy con chung dài nhất (LCS), kiểm tra mẫu | Kadane’s Algorithm, tìm tổng lớn nhất, chia hết… |
✅ = Có yêu cầu, ❌ = Không yêu cầu