資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理
化學
生物
數學
英語
經濟學
心理學
社會研究
時尚研究
法律研究在 C++ 中查詢陣列的所有不同子集（或子序列）和
假設我們有一組整數。找到給定集合的子集可以形成的不同和，並按升序打印出來。陣列元素的和很小。考慮 [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
更新於： 2019 年 11 月 1 日
374 次瀏覽
廣告