查找C ++中数组的所有不同子集（或子序列）总和

  • Z时代
  • 2024-01-10
  • 分类：综合

假设我们有一组整数。查找可以从给定集合的子集形成的不同总和，并以升序打印。数组元素的总和很小。考虑一下数组元素就像[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

以上是 查找C ++中数组的所有不同子集（或子序列）总和 的全部内容， 来源链接： utcz.com/z/345472.html

回到顶部