สมมุติว่าเรามีเซตของจำนวนเต็ม ค้นหาผลรวมเฉพาะซึ่งสามารถเกิดขึ้นได้จากชุดย่อยของชุดที่กำหนดและพิมพ์ตามลำดับจากน้อยไปมาก ผลรวมขององค์ประกอบอาร์เรย์มีขนาดเล็ก พิจารณาว่าองค์ประกอบอาร์เรย์เป็นเหมือน [1, 2, 3] เอาต์พุตจะเป็น 0, 1, 2, 3, 4, 5, 6 เซตย่อยที่แตกต่างกันคือ {}, {1}, {2}, {3}, {1, 2}, {2, 3}, {1 , 3}, {1, 2, 3}, ค่าผลรวมคือ 0, 1, 2, 3, 3, 5, 4, 6
เพื่อแก้ปัญหานี้ เราจะใช้วิธีการเขียนโปรแกรมแบบไดนามิก เมื่อผลรวมขององค์ประกอบที่กำหนดมีขนาดเล็ก เราสามารถสร้างตาราง DP ที่มีแถวที่มีขนาดของอาร์เรย์ และขนาดของคอลัมน์จะเป็นผลรวมขององค์ประกอบทั้งหมดในอาร์เรย์ที่กำหนด
ตัวอย่าง
#include<iostream>
#include<cstring>
using namespace std;
void displaySubsetSum(int arr[], int n) {
int sum = 0;
for (int i=0; i<n; i++)
sum += arr[i];
bool table[n+1][sum+1];
memset(table, 0, sizeof(table));
for (int i=0; i<=n; i++)
table[i][0] = true;
for (int i=1; i<=n; i++) {
table[i][arr[i-1]] = true;
for (int j=1; j<=sum; j++) {
if (table[i-1][j] == true) {
table[i][j] = true;
table[i][j + arr[i-1]] = true;
}
}
}
for (int j=0; j<=sum; j++)
if (table[n][j]==true)
cout << j << " ";
}
int main() {
int arr[] = {1, 2, 3};
int n = sizeof(arr)/sizeof(arr[0]);
displaySubsetSum(arr, n);
} ผลลัพธ์
0 1 2 3 4 5 6
