Tất cả bộ ba (triplets) duy nhất có tổng bằng giá trị cho trước (C++)

Cho mảng các phần tử và một giá trị tổng S. Tìm tất cả các bộ ba (triplets) từ mảng có tổng bằng S. Ví dụ mảng {4, 8, 63, 21, 24, 3, 6, 1, 0}, S = 18. Bộ ba là {4, 6, 8}. Nếu có nhiều bộ ba, hiển thị tất cả.

Thuật toán

getTriplets(arr, n, sum) –

Bắt đầu
    trip_arr lưu các bộ ba
    unique_trip (set) lưu bộ ba duy nhất, tránh trùng lặp
    sắp xếp arr
    for i = 0 đến n-2:
        j = i+1, k = n-1
        while j < k:
            nếu arr[i]+arr[j]+arr[k] == sum:
                temp = arr[i]:arr[j]:arr[k]
                nếu temp không trong unique_trip:
                    thêm vào unique_trip
                    tạo newTriplet, thêm vào trip_arr
                j++, k--
            else nếu tổng > sum: k--
            else: j++
    hiển thị tất cả bộ ba
Kết thúc

Ví dụ mã C++

#include <iostream> 
#include <vector> 
#include <set> 
#include <algorithm> 
using namespace std; 

class triplet { 
    public: 
    int first, second, third; 
    void display() { 
        cout << "(" << first << ", " << second << ", " << third << ")" << endl; 
    } 
}; 

int getTriplets(int arr[], int n, int sum) { 
    int i, j, k; 
    vector<triplet> triplets; 
    set<string> uniqTriplets; 
    string temp_triplet; 
    triplet newTriplet; 
    sort(arr, arr + n); 
    for (i = 0; i < n - 2; i++) { 
        j = i + 1; 
        k = n - 1; 
        while (j < k) { 
            if (arr[i] + arr[j] + arr[k] == sum) { 
                temp_triplet = to_string(arr[i]) + " : " + to_string(arr[j]) + " : " + to_string(arr[k]); 
                if (uniqTriplets.find(temp_triplet) == uniqTriplets.end()) { 
                    uniqTriplets.insert(temp_triplet); 
                    newTriplet.first = arr[i]; 
                    newTriplet.second = arr[j]; 
                    newTriplet.third = arr[k]; 
                    triplets.push_back(newTriplet); 
                } 
                j++; k--; 
            } else if (arr[i] + arr[j] + arr[k] > sum) 
                k--; 
            else 
                j++; 
        } 
    } 
    if (triplets.size() == 0) return 0; 
    for (i = 0; i < triplets.size(); i++) 
        triplets[i].display(); 
} 

int main() { 
    int nums[] = {4, 8, 63, 21, 24, 3, 6, 1, 0, 5}; 
    int n = sizeof(nums) / sizeof(nums[0]); 
    int sum = 27; 
    if (!getTriplets(nums, n, sum)) 
        cout << "Không thể tạo bộ ba nào."; 
}

Kết quả

(0, 3, 24) 
(0, 6, 21) 
(1, 5, 21)