यहां हम एक दिलचस्प समस्या देखेंगे। हमारे पास कुछ तत्वों के साथ एक सरणी है। एक योग मान दिया गया है। हमारा कार्य सरणी से ट्रिपलेट्स ढूंढना है, और जिनका योग दिए गए योग के समान है। मान लीजिए सरणी है {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)
