এখানে আমরা একটি रोचক সমস্যা দেখব। আমাদের একটি অ্যারে আছে কিছু এলিমেন্টসহ। একটি সম মান দেওয়া আছে। আমাদের টাস্ক হলো অ্যারে থেকে ট্রিপলেট বের করা, যাদের যোগফল দেওয়া সমের সমান। মনে করুন অ্যারেটি {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)
