In Tất Cả Các Cặp Trong Mảng Không Sắp Xếp Có Tổng Bằng Nhau Trong C++

Trong bài toán này, chúng ta có một mảng không sắp xếp và phải in tất cả các cặp trong mảng có tổng bằng nhau.

Ví dụ để hiểu vấn đề:

Đầu vào: mảng = [12, 13, 20, 5] → Đầu ra: [12, 13] và [20, 5] có tổng 25.

Để giải quyết, ta tìm các cặp có tổng giống nhau. Kiểm tra các cặp và dùng map để tránh cặp trùng lặp.

Cần hai map: một lưu tất cả cặp và tổng của chúng, một lưu tổng và vector các cặp tương ứng.

Map1 → key = cặp; value → tổng

Map2 → key = tổng (số nguyên); value → vector cặp

In tất cả giá trị có cùng tổng.

Ví Dụ

Chương trình minh họa logic:

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

void findEqualSumPairs(int A[], int n) {
    map<int, vector<pair<int, int>>> map1;
    for (int i = 0; i < n - 1; i++) {
        for (int j = i + 1; j < n; j++) {
            pair<int, int> p = make_pair(A[i], A[j]);
            map1[A[i] + A[j]].push_back(p);
        }
    }
    for (auto value = map1.begin(); value != map1.end(); value++) {
        if (value->second.size() > 1) {
            for (int i = 0; i < value->second.size(); i++) {
                cout << "[ " << value->second[i].first << ", " << value->second[i].second << "] ";
            }
            cout << "có tổng: " << value->first << endl;
        }
    }
}

int main() {
    int A[] = { 6, 4, 12, 10, 22, 11, 8, 2 };
    int n = sizeof(A) / sizeof(A[0]);
    cout << "Các cặp có tổng bằng nhau là:\n";
    findEqualSumPairs(A, n);
    return 0;
}

Đầu Ra

Các cặp có tổng bằng nhau là:

[ 6, 4] [ 8, 2] có tổng: 10
[ 4, 8] [ 10, 2] có tổng: 12
[ 6, 8] [ 4, 10] [ 12, 2] có tổng: 14
[ 6, 10] [ 4, 12] có tổng: 16
[ 6, 12] [ 10, 8] có tổng: 18