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