หา Triplets ทั้งหมดที่ไม่ซ้ำกันซึ่งผลรวมเท่ากับค่าที่กำหนดใน C++

ที่นี่เราจะดูปัญหาที่น่าสนใจ เรามีอาร์เรย์ที่มีองค์ประกอบบางส่วน มีค่าผลรวม (sum value) ให้ งานของเราคือหา triplets จากอาร์เรย์ ที่ผลรวมเท่ากับค่าที่กำหนด สมมติอาร์เรย์คือ {4, 8, 63, 21, 24, 3, 6, 1, 0} และค่าผลรวม S = 18 ดังนั้น triplets จะเป็น {4, 6, 8} หากมี triplet มากกว่าหนึ่ง จะแสดงทั้งหมด

อัลกอริทึม

getTriplets(arr, n, sum):

Begin
    กำหนดอาร์เรย์หนึ่งเพื่อเก็บ triplets ว่า trip_arr
    กำหนด set unique_trip เพื่อเก็บ triplets ที่ไม่ซ้ำกัน ไม่จะมี triplet ซ้ำ
    เรียงลำดับ arr
    for i ในช่วง 0 ถึง n-2:
        j := i + 1, และ k := n - 1
        while (j < k):
            ถ้า arr[i] + arr[j] + arr[k] = sum:
                temp := arr[i] : arr[j] : arr[k]
                ถ้า temp ไม่อยู่ใน unique_trip:
                    แทรก temp เข้า unique_trip set
                    สร้าง newTriplet ด้วย arr[i] arr[j] arr[k]
                    เพิ่ม newTriplet เข้า trip_arr
                endif
                เพิ่ม j, ลด k
            มิฉะนั้นถ้า arr[i] + arr[j] + arr[k] > sum:
                ลด k
            มิฉะนั้น:
                เพิ่ม j
            end if
        done
    done
    แสดง triplets ทั้งหมด
End

ตัวอย่างโค้ด

#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; // ใช้ set เพื่อป้องกัน triplet ซ้ำ
    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 << "No triplets can be formed.";
}

ผลลัพธ์

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