정수 집합이 있다고 가정합니다. 주어진 집합의 하위 집합에서 형성될 수 있는 고유한 합계를 찾아 오름차순으로 인쇄합니다. 배열 요소의 합이 작습니다. 배열 요소가 [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