N तत्वों के सभी संयोजनों को चिन्ह बदलकर इस प्रकार प्रिंट करें कि उनका योग C++ में M से विभाज्य हो

इस समस्या में, हमें N तत्वों की एक सरणी दी गई है। और सभी तत्वों के योग को एक पूर्णांक एम से विभाजित करने की आवश्यकता है।

Input : array = {4, 7, 3} ; M = 3
Output : 5+4+3 ; 5+4-3

इस समस्या को हल करने के लिए, हमें एक पावर सेट की अवधारणा को जानना होगा जिसका उपयोग प्राप्त सभी संभावित योगों को खोजने के लिए किया जा सकता है। इस राशि से, उन सभी को प्रिंट करें जो M से विभाज्य हैं।

एल्गोरिदम

Step 1: Iterate overall combinations of ‘+’ and ‘-’ using power set.
Step 2: If the sum combination is divisible by M, print them with signs.

उदाहरण

#include <iostream>
using namespace std;
void printDivisibleSum(int a[], int n, int m){
   for (int i = 0; i < (1 << n); i++) {
      int sum = 0;
      int num = 1 << (n - 1);
      for (int j = 0; j < n; j++) {
         if (i & num)
            sum += a[j];
         else
            sum += (-1 * a[j]);
         num = num >> 1;
      }
      if (sum % m == 0) {
         num = 1 << (n - 1);
         for (int j = 0; j < n; j++) {
            if ((i & num))
               cout << "+ " << a[j] << " ";
            else
               cout << "- " << a[j] << " ";
            num = num >> 1;
         }
         cout << endl;
      }
   }
}
int main(){
   int arr[] = {4,7,3};
   int n = sizeof(arr) / sizeof(arr[0]);
   int m = 3;
   cout<<"The sum combination divisible by n :\n";
   printDivisibleSum(arr, n, m);
   return 0;
}

आउटपुट

योग संयोजन n से विभाज्य है -

- 4 + 7 - 3
- 4 + 7 + 3
+ 4 - 7 - 3
+ 4 - 7 + 3