Trong bài toán này, chúng ta được cung cấp một mảng gồm N phần tử. Và cần trả về tổng của các phần tử chia hết cho số nguyên M.
Input : array = {4, 7, 3} ; M = 3
Output : 5+4+3 ; 5+4-3 Để giải quyết vấn đề này, chúng ta cần biết khái niệm về một tập hợp lũy thừa có thể được sử dụng để tìm tất cả các tổng có thể có được. Từ tổng này, in ra tất cả các số chia hết cho M.
Thuật toán
Step 1: Iterate overall combinations of ‘+’ and ‘-’ using power set. Step 2: If the sum combination is divisible by M, print them with signs.
Ví dụ
#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;
} Đầu ra
Tổ hợp tổng chia hết cho n -
- 4 + 7 - 3 - 4 + 7 + 3 + 4 - 7 - 3 + 4 - 7 + 3