11
\$\begingroup\$

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^n space)?
Also, is there any scope of improving time or space without trading-off the other?

\$\endgroup\$
10
\$\begingroup\$

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::ispow2(i) (after you make i unsigned). The aforementioned power2 function can also be improved with concepts:

// returns 2^n
template <std::UnsignedIntegral 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;
}
\$\endgroup\$
  • 3
    \$\begingroup\$ Arguably, it makes sense to use a different type for the sum, as it likely has to represent a bigger range. Unfortunately, we don't know whether long long actually does have a bigger range than int (both could be simple 64-bit values, for example). \$\endgroup\$ – Toby Speight Jul 26 at 12:45
  • \$\begingroup\$ Great analysis. I now have things to learn about, like std::transform \$\endgroup\$ – Gaurav Singh Jul 26 at 16:19
  • 3
    \$\begingroup\$ exponential space algorithms are never "great". \$\endgroup\$ – Will Ness Jul 27 at 7:05
  • 1
    \$\begingroup\$ @WillNess Good point. I just saw your answer and upvoted. Although I never said this algorithm is great :) \$\endgroup\$ – L. F. Jul 27 at 7:11
  • \$\begingroup\$ I've edited, to clarify some points. :) \$\endgroup\$ – Will Ness Jul 27 at 7:13
6
\$\begingroup\$

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 n, 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.

\$\endgroup\$
  • \$\begingroup\$ You can emulate the loops with recursive function calls. using recursion, I see how to not need different source code for different n. \$\endgroup\$ – greybeard Jul 27 at 3:36
  • 1
    \$\begingroup\$ (Down-voters please comment. The tool-tip I get reads not useful.) \$\endgroup\$ – greybeard Jul 27 at 4:35
  • \$\begingroup\$ @greybeard that was the point, yes. some languages actually do allow you to create (the equivalent of) nested loops in run time, which is what I meant obviously (by "create"), not the hard coded n loops. But in C and derivatives, recursion can do that. -- Re "useful", right now we have an exponential space algo at +9 votes, and a linear space algo at -1. Just NB. -- also, with recursion, for isn;t needed, it can be inlined. I wrote it that way so that correctness is self-evident. \$\endgroup\$ – Will Ness Jul 27 at 6:50
  • \$\begingroup\$ Also, this idea can be generalized with output iterators, so that the caller can customize the output format, or choose to store the results somewhere, etc. \$\endgroup\$ – L. F. Jul 27 at 7:20
  • \$\begingroup\$ Using recursion seems like a better idea than my algorithm (same time, less space). But it will also use call stack. Don't we need to consider that? Edit : Sorry, my bad. Call stack will take max n space at any time. Realized after commenting. \$\endgroup\$ – Gaurav Singh Jul 27 at 7:34
3
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ There are just too many ways to use this in an implementation for me to decide on one, starting with bothering not to limit array length to number of bits in a suitable integer type. \$\endgroup\$ – greybeard Jul 27 at 4:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.