Thuật toán duyệt phân tập

Bài toán cơ bản: Cho mảng A[1..n] đếm số dãy con của mảng có tổng bằng S với n<=40.

• Inp: n, S, mảng A.
• Out: kết quả bài toán.

Inp:

4 4

1 2 3 4

Out:

2

Các dãy con: (4) , (1,3)

Phân tích: 

• Thuật toán ta nghĩ ra ngay là duyệt dãy nhị phân 01
• Nhưng duyệt chỉ giải quyết được với n <= 20. Chính vì vậy phải dùng thuật toán duyệt phân tập mới có thể ăn full test 🙂

Tư tưởng thuật toán duyệt phân tập:

• Chia mảng A làm 2 mảng nhỏ độ dài n/2
• Khi đó max(n/2)=20 => duyệt
• Khi duyệt các mảng nhỏ ta lưu tổng các dãy con của mảng nhỏ vào các mảng riêng S1[] và S2[]
• Với mỗi giá trị S1[] ta tìm kiếm nhị phần trong S2[] phần tử có giá trị S-S1[i] (cộng res với số gt S-S1[i] trong S2[]
• res là kết quả bài toán

Các bài tập:

http://yeulaptrinh.de/312/coin34-spoj/
http://yeulaptrinh.de/673/vector-spoj/