Tất cả các bộ ba duy nhất tổng hợp thành một giá trị nhất định trong C ++

Ở đây chúng ta sẽ thấy một vấn đề thú vị. Chúng ta có một mảng với một số phần tử. Một giá trị tổng được đưa ra. Nhiệm vụ của chúng ta là tìm các bộ ba từ mảng và có tổng bằng tổng đã cho. Giả sử mảng là {4, 8, 63, 21, 24, 3, 6, 1, 0} và giá trị tổng là S =18. Vậy các bộ ba sẽ là {4, 6, 8}. Nếu có nhiều hơn một bộ ba, nó sẽ hiển thị tất cả chúng.

Thuật toán

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

Ví dụ

#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.";
}

Đầu ra

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