सभी अद्वितीय ट्रिपल जो 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)