Đếm số bộ bốn (quadruplets) có tổng bằng giá trị cho trước trong C++

Cho bốn mảng A, B, C, D. Mục tiêu là đếm số lượng bộ bốn (quadruplets) lấy một phần tử từ mỗi mảng sao cho tổng của chúng bằng giá trị Sum cho trước.

Ví dụ minh họa

Ví dụ 1:

• Input: A={1,3,1}, B={2,4,5}, C={1,1,2}, D={4,4,0}, Sum=5
• Output: 2
• Giải thích: Hai bộ bốn: (1,2,2,0) từ A[0],B[0],C[2],D[2] và (1,2,2,0) từ A[2],B[0],C[2],D[2].

Ví dụ 2:

• Input: A={1,1,1}, B={1,1,1}, C={1,1,1}, D={1,1,1}, Sum=3
• Output: 0
• Giải thích: Tổng bất kỳ bộ bốn nào đều là 4 > 3.

Thuật toán cơ bản (Vét cạn)

Sử dụng 4 vòng lặp lồng nhau để duyệt tất cả các tổ hợp có thể. Độ phức tạp O(n⁴) với n là kích thước mảng.

Mã nguồn C++ (Vét cạn)

#include <bits/stdc++.h>
using namespace std;

int quadruplets(int first[], int second[], int third[], int fourth[],
                int first_size, int second_size, int third_size, int fourth_size, int sum) {
    int count = 0;
    for (int i = 0; i < first_size; i++) {
        for (int j = 0; j < second_size; j++) {
            for (int k = 0; k < third_size; k++) {
                for (int l = 0; l < fourth_size; l++) {
                    if (first[i] + second[j] + third[k] + fourth[l] == sum) {
                        count++;
                    }
                }
            }
        }
    }
    return count;
}

int main() {
    int first[] = {7, -8};
    int second[] = {7, -2};
    int third[] = {4, -2};
    int fourth[] = {3, -4};
    int first_size = sizeof(first) / sizeof(first[0]);
    int second_size = sizeof(second) / sizeof(second[0]);
    int third_size = sizeof(third) / sizeof(third[0]);
    int fourth_size = sizeof(fourth) / sizeof(fourth[0]);
    int sum = 0;
    cout << "So bo bon co tong bang " << sum << ": " << quadruplets(first, second, third, fourth,
         first_size, second_size, third_size, fourth_size, sum);
    return 0;
}

Kết quả chạy chương trình

So bo bon co tong bang 0: 1

Tối ưu hóa (Quan trọng)

Với mảng lớn, O(n⁴) quá chậm. Có thể giảm xuống O(n² log n) hoặc O(n²) bằng kỹ thuật Meet-in-the-middle:

1. Tính tất cả tổng cặp từ A+B lưu vào mảng AB, và C+D lưu vào mảng CD.
2. Sắp xếp mảng CD.
3. Với mỗi giá trị x trong AB, tìm số lần xuất hiện của (sum - x) trong CD bằng binary search.

Mã nguồn tối ưu O(n² log n)

#include <bits/stdc++.h>
using namespace std;

int quadruplets_optimized(vector<int>& A, vector<int>& B, 
                          vector<int>& C, vector<int>& D, int sum) {
    vector<int> AB, CD;
    for (int a : A) for (int b : B) AB.push_back(a + b);
    for (int c : C) for (int d : D) CD.push_back(c + d);
    
    sort(CD.begin(), CD.end());
    
    long long count = 0;
    for (int x : AB) {
        int target = sum - x;
        auto range = equal_range(CD.begin(), CD.end(), target);
        count += range.second - range.first;
    }
    return count;
}