ในปัญหานี้ เราจะได้รับ array ของ N องค์ประกอบ และต้องหา combinations ของผลรวมขององค์ประกอบที่หารด้วยจำนวนเต็ม M ลงตัว
Input: array = {4, 7, 3} ; M = 3
Output: 5+4+3 ; 5+4-3
เพื่อแก้ปัญหานี้ เราต้องรู้แนวคิดของ power set ที่ใช้หา ผลรวมที่เป็นไปได้ทั้งหมด จากผลรวมนี้ ให้พิมพ์เฉพาะที่หาร M ลงตัว
อัลกอริทึม
ขั้นตอนที่ 1: วนลูปทุก combinations ของ '+' และ '-' โดยใช้ power set ขั้นตอนที่ 2: ถ้า sum combination หาร M ลงตัว ให้พิมพ์พร้อมเครื่องหมาย
โปรแกรมตัวอย่าง
#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;
}
ผลลัพธ์
The sum combination is divisible by n -
- 4 + 7 - 3 - 4 + 7 + 3 + 4 - 7 - 3 + 4 - 7 + 3
