本文共 2250 字，大约阅读时间需要 7 分钟。

原文地址：

Given an array of integers, print sums of all subsets in it. Output sums can be printed in any order.

Input : arr[] = {2, 3}Output: 0 2 3 5Input : arr[] = {2, 4, 5}Output : 0 2 4 5 6 7 9 11

Method 1 (Recursive)

We can recursively solve this problem. There are total 2 ⁿ subsets. For every element, we consider two choices, we include it in a subset and we don’t include it in a subset. Below is recursive solution based on this idea.

方法一（递归）

我们可以递归地解决这个问题，这个集合共有2ⁿ个子集。对于每一个元素，我们考虑两种选择，子集中包含这个元素或者不包含这个元素。下面是基于这个想法的递归方法。

// C++ program to print sums of all possible// subsets.#include
   
    using namespace std; // Prints sums of all subsets of arr[l..r]void subsetSums(int arr[], int l, int r,                int sum=0){    // Print current subset    if (l > r)    {        cout << sum << " ";        return;    }     // Subset including arr[l]    subsetSums(arr, l+1, r, sum+arr[l]);     // Subset excluding arr[l]    subsetSums(arr, l+1, r, sum);} // Driver codeint main(){    int arr[] = {5, 4, 3};    int n = sizeof(arr)/sizeof(arr[0]);     subsetSums(arr, 0, n-1);    return 0;}
   

Output:

12 9 8 5 7 4 3 0

Method 2 (Iterative)

As discussed above, there are total 2 ⁿ subsets. The idea is generate loop from 0 to 2 ⁿ – 1. For every number, pick all array elements which correspond to 1s in binary representation of current number.

方法二（迭代）

正如前面所讨论的，这个集合有2ⁿ个子集。这个想法就是从0到2ⁿ – 1循环。对于每个数字，挑出所有的数组元素，这些元素表示出二进制的时候每一位全部是1.

// Iterative C++ program to print sums of all// possible subsets.#include
   
    using namespace std; // Prints sums of all subsets of arrayvoid subsetSums(int arr[], int n){    // There are totoal 2^n subsets    long long total = 1<
   

Output:

12 9 8 5 7 4 3 0

Thanks to cfh for suggesting above iterative solution in a comment.

Note: We haven’t actually created sub-sets to find their sums rather we have just used recursion to find sum of non-contiguous sub-sets of the given set.

The above mentioned techniques can be used to perform various operations on sub-sets like multiplication, division, XOR, OR, etc, without actually creating and storing the sub-sets and thus making the program memory efficient.

注意：我们还没有真正创建子集来得到它们的值，而是我们只是用递归得到已知集合子集的非连续和。

以上所提到的技术可以用于各种子集的操作，例如：乘法、除法、XOR、OR等，没有真正创建并存储子集，因此可以使得代码使用内存更有效。

转载地址：http://cgqii.baihongyu.com/