Giả sử chúng ta có một tập hợp các số nguyên. Tìm tổng riêng biệt, có thể được tạo thành từ tập con của các tập hợp đã cho và in chúng theo thứ tự tăng dần. Tổng các phần tử của mảng là nhỏ. Coi các phần tử của mảng giống như [1, 2, 3]. Đầu ra sẽ là 0, 1, 2, 3, 4, 5, 6. Các tập con riêng biệt là {}, {1}, {2}, {3}, {1, 2}, {2, 3}, {1 , 3}, {1, 2, 3}, các giá trị tổng là 0, 1, 2, 3, 3, 5, 4, 6.
Để giải quyết vấn đề này, chúng tôi sẽ sử dụng phương pháp lập trình động. Khi tổng của phần tử đã cho nhỏ, chúng ta có thể tạo bảng DP với các hàng chứa kích thước của mảng và kích thước của cột sẽ là tổng của tất cả các phần tử trong mảng đã cho.
Ví dụ
#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);
} Đầu ra
0 1 2 3 4 5 6