Print sums of all subsets 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&lt;iostream&gt;
#include&lt;vector&gt;
//using namespace std;

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

std::vector&lt;long long&gt; subsetSums(std::vector&lt;int&gt; set)
{
    long long total = 1&lt;&lt;set.size();    //total number of subsets = size of power set = 2^n
    std::vector&lt;long long&gt; sums(total, 0);
    sums[1] = set[0];
    //std::cout &lt;&lt; sums[0] &lt;&lt; std::endl;
    //std::cout &lt;&lt; sums[1] &lt;&lt; std::endl;
    int effectiveBits = 1, prevPowOf2 = 1;
    for (long long i = 2; i &lt; total; ++i)
    {
        if (isPowerOf2(i))
        {
            ++effectiveBits;
            prevPowOf2 *= 2;
        }
        //std::cout &lt;&lt; "e = " &lt;&lt; effectiveBits &lt;&lt; "\tp = " &lt;&lt; prevPowOf2 &lt;&lt; std::endl;

        sums[i] = set[effectiveBits-1] + sums[i-prevPowOf2];
        //std::cout &lt;&lt; sums[i] &lt;&lt; "\n";
    }

    return sums;
}

// Driver code
int main()
{
    std::vector&lt;int&gt; set = {5, 4, 3};

    std::vector&lt;long long&gt; sumsOfAllSubsets = subsetSums(set);
    for (auto sum : sumsOfAllSubsets)
        std::cout &lt;&lt; sum &lt;&lt; "\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^n space)?
Also, is there any scope of improving time or space without trading-off the other?
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 &lt;bits/stdc++.h&gt;.  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&lt;long long&gt; subsetSums(const std::vector&lt;int&gt;&amp; set)
{
    std::vector&lt;long long&gt; subset_sums{0};
    subset_sums.reserve(std::size_t(1) &lt;&lt; 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 &lt;algorithm&gt; for std::transform and #include &lt;iterator&gt; 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:


The initial list of sums is {0}.
For the first element 5, the list becomes {0, 5}, where 5 = 0 + 5.
For the second element 4, the list becomes {0, 5, 4, 9}, where {4, 9} = {0, 5} + 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 &lt;iostream&gt;.  And simply delete using namespace std; rather than commenting it out to show you are following good practice&nbsp;:)

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 &amp;&amp; !(x &amp; (x - 1));
}


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

// returns 2^n
template &lt;typename T, std::enable_if_t&lt;std::is_integral_v&lt;T&gt; &amp;&amp; is_unsigned_v&lt;T&gt;, int&gt; = 0&gt;
constexpr T power2(T n)
{
    assert(n &lt; std::numeric_limits&lt;T&gt;::digits);
    return T(1) &lt;&lt; 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::ispow2(i) (after you make i unsigned).  The aforementioned power2 function can also be improved with concepts:

// returns 2^n
template &lt;std::UnsignedIntegral T&gt;
constexpr T power2(T n)
{
    assert(n &lt; std::numeric_limits&lt;T&gt;::digits);
    return T(1) &lt;&lt; n;
}


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

std::vector&lt;number_t&gt; subsetSums(const std::vector&lt;number_t&gt;&amp; set)
{
    std::vector&lt;number_t&gt; subset_sums{0};
    subset_sums.reserve(std::size_t(1) &lt;&lt; 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;
}