Print sums of all subsets

Question

Print sums of all subsets of a given set

Problem summary : Print all subset sums of a given set of integers

My approach is to store previous results and use them to calculate new (similar idea as DP).

SubsetSum.cpp

#include<iostream>
#include<vector>
//using namespace std;

bool isPowerOf2 (long long x)
{
  /* First x in the below expression is for the case when x is 0 */
    return x && (!(x&(x-1)));
}

std::vector<long long> subsetSums(std::vector<int> set)
{
    long long total = 1<<set.size();    //total number of subsets = size of power set = 2^n
    std::vector<long long> sums(total, 0);
    sums[1] = set[0];
    //std::cout << sums[0] << std::endl;
    //std::cout << sums[1] << std::endl;
    int effectiveBits = 1, prevPowOf2 = 1;
    for (long long i = 2; i < total; ++i)
    {
        if (isPowerOf2(i))
        {
            ++effectiveBits;
            prevPowOf2 *= 2;
        }
        //std::cout << "e = " << effectiveBits << "\tp = " << prevPowOf2 << std::endl;
        
        sums[i] = set[effectiveBits-1] + sums[i-prevPowOf2];
        //std::cout << sums[i] << "\n";
    }
    
    return sums;
}
 
// Driver code
int main()
{
    std::vector<int> set = {5, 4, 3};
 
    std::vector<long long> sumsOfAllSubsets = subsetSums(set);
    for (auto sum : sumsOfAllSubsets)
        std::cout << sum << "\n";
    return 0;
}

You can find the code on Github Gist and compilation result at OnlineGdb.

Along with code, please also comment on the algorithm itself.
Is it advisable to store previous result in practice (since it takes 2ⁿ space)?
Also, is there any scope of improving time or space without trading-off the other?

Answer 1

Preface

This is great code. Your solution is more than \$10^{42}\$ times nicer than the given solutions on the linked page that promote crap like #include <bits/stdc++.h>. You are already much better than them in this regard.

The algorithm

Making use of the STL, your algorithm can be simplified like this:

std::vector<long long> subsetSums(const std::vector<int>& set)
{
    std::vector<long long> subset_sums{0};
    subset_sums.reserve(std::size_t(1) << set.size()); // to prevent iterator invalidation
    for (int num : set)
        std::transform(subset_sums.begin(), subset_sums.end(),
                       std::back_inserter(subset_sums),
                       [=](number_t prev_sum){ return prev_sum + num; });
    return subset_sums;
}

(You need #include <algorithm> for std::transform and #include <iterator> for std::back_inserter) Here, we first push 0 to the list of sums. Then, for each element \$x\$, we add \$x\$ to the previous sums and push these new sums. Therefore:

1. The initial list of sums is {0}.

2. For the first element 5, the list becomes {0, 5}, where 5 = 0 + 5.

3. For the second element 4, the list becomes {0, 5, 4, 9}, where {4, 9} = {0, 5} + 4.

4. For the third element 3, the list becomes {0, 5, 4, 9, 3, 8, 7, 12}, where {3, 8, 7, 12} = {0, 5, 4, 9} + 3.

Miscellaneous

The common practice is to put a space between #include and the header name, as in #include <iostream>. And simply delete using namespace std; rather than commenting it out to show you are following good practice :)

You use int for the original numbers, and long long for the sums. Don't mix different data types. Write a type alias like

using number_t = long long;

And use it consistently throughout your code. This makes it clear what these types are used for.

i should really be of an unsigned type. And isPowerOf2 should also operate on an unsigned type. The isPowerOf2 function can be made constexpr. And I prefer a looser layout with more spaces and less parentheses:

constexpr bool isPowerOf2(std::size_t x)
{
  /* First x in the below expression is for the case when x is 0 */
    return x && !(x & (x - 1));
}

1 << set.size() potentially overflows. std::size_t(1) << set.size() is better. For me, it may be better to extract a function and check for overflow:

// returns 2^n
template <typename T, std::enable_if_t<std::is_integral_v<T> && is_unsigned_v<T>, int> = 0>
constexpr T power2(T n)
{
    assert(n < std::numeric_limits<T>::digits);
    return T(1) << n;
}

Passing a std::vector by value may cause unnecessary copies. Pass by const reference instead.

return 0; can be omitted for the main function.

The future

C++20 provides us with bit manipulation utilities. We can replace isPowerOf2(i) with std::has_single_bit(i) (after you make i unsigned). The aforementioned power2 function can also be improved with concepts:

// returns 2^n
template <std::unsigned_integral T>
constexpr T power2(T n)
{
    assert(n < std::numeric_limits<T>::digits);
    return T(1) << n;
}

The algorithm can also be simplified with the Ranges library and std::bind_front:

std::vector<number_t> subsetSums(const std::vector<number_t>& set)
{
    std::vector<number_t> subset_sums{0};
    subset_sums.reserve(std::size_t(1) << set.size());
    for (int num : set)
        ranges::push_back(subset_sums,
            subset_sums | ranges::view::transform(std::bind_front(ranges::plus, num)));
    return subset_sums;
}

Answer 2

This is bad. You calculate them all first, and only then print them out. And what if n = 20, or 42, or 100? The printout will never start (and the memory will blow up before that, too).

Instead, have your program create n nested loops at run-time, in effect enumerating the binary encoding of 2ⁿ, and print the sums out from the innermost loop. In pseudocode:

 // {5, 4, 3}
 sum = 0
 for x in {5, 0}:   // included, not included
     sum += x
     for x in {4, 0}:
         sum += x
         for x in {3, 0}:
             sum += x
             print sum
             sum -= x
         sum -= x
     sum -= x

You can emulate the loops creation with recursion, coding only one recursive function. Pass it the array ({5, 4, 3} in your example) and a zero-based index, and work as shown above with x in {arr[i], 0}, making the recursive call with i+1, if i is in bounds (i < n); or print the sum value out, otherwise. The for loop can be inlined away as well, since there always are only two numbers to process, arr[i] and 0.

You did say print. Storing them is an insanely ginormous overkill.

edit: Thus concludes the algorithmic review, which you did request. No point to reviewing the code when algorithm is unsuitable for the task. Exponential space algorithms are never good when there's a linear space algorithm to be had.

2022 side note: print can be replaced with any odd callback of your choosing (emulating Prolog / nondeterministic programming, somewhat). See also "recursive backtracking". (the linked SO answers of mine are using Lisp mostly, but there's some pseudocode in there as well).

Answer 3

Said before, but not by me: storing even half of the final result is not advisable.

An n-bit Gray-code assumes every combination of n values of 0 (use for not included) and 1 (included) - while only changing one bit in every transition:
start with code and sum 0
for the changing bit i turning to one, add the ith array item
subtract for a change from one to zero