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