সমস্ত অনন্য ট্রিপলেট যা C++ এ একটি প্রদত্ত মান পর্যন্ত যোগ করে

এখানে আমরা একটি আকর্ষণীয় সমস্যা দেখতে পাব। আমরা কিছু উপাদান সঙ্গে একটি অ্যারে আছে. একটি সমষ্টি মান দেওয়া হয়. আমাদের কাজ হল অ্যারে থেকে ট্রিপলেট খুঁজে বের করা এবং যার যোগফল প্রদত্ত যোগফলের সমান। ধরুন অ্যারেটি হল {4, 8, 63, 21, 24, 3, 6, 1, 0}, এবং যোগফলের মান হল S =18। তাই ট্রিপলেটগুলি হবে {4, 6, 8}। যদি একাধিক ট্রিপলেট উপস্থিত থাকে তবে এটি তাদের সবগুলি দেখাবে৷

অ্যালগরিদম

getTriplets(arr, n, sum) −

Begin
   define one array to store triplets, say trip_arr
   define one set unique_trip to store unique triplets. No same triplets will be their.
   sort arr
   for i in range 0 to n-2, do
      j :- i + 1, and k := n – 1
      while(j < k), do
         if arr[i] + arr[j] + arr[k] = sum, then
            temp := arr[i] : arr[j] : arr[k]
            if temp is not present into the unique_trip, then
               insert temp into unique_trip set
               create newTriplet using arr[i] arr[j] and arr[k]
               add newTriplet into trip_arr
            endif
            increase j, and decrease k
         else if arr[i] + arr[j] + arr[k] > sum
            decrease k
         else
            increase j
         end if
      done
   done
   display all 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; //use set to avoid duplicate triplets
   string temp_triplet;
   triplet newTriplet;
   sort(arr, arr + n); //sort the array
   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)