9
\$\begingroup\$

Background

A recent question Print sums of all subsets made its way to the Hot Network Questions list. The problem is simple:

Print sums of all subsets of a given set

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

Examples:

Input : arr[] = {2, 3}
Output: 0 2 3 5

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

(Source)

The OP used an exponential space algorithm. I didn't care about this too much in my answer, but later an answer by Will Ness noted that exponential space is not required. The better algorithm works like this: (to quote that answer)

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

I decided to implement this algorithm.

Code

I wrote the code in C++17. subset_sums is a generic algorithm which gives the results to an output iterator, so the user can choose to output the results or store them immediately, or customize the output format if they want, etc. I am influenced a lot by the Range-v3 library, so my algorithm uses iterator-sentinel pairs instead of the traditional iterator-iterator pairs, and it also supports projections. This code does not use the Range-v3 library, though. The identity function object type is standardized in C++20, so I rolled out my own version.

#include <functional>
#include <iterator>
#include <utility>

namespace util {
    struct identity {
        using is_transparent = int;

        template <typename T>
        constexpr T&& operator()(T&& arg) const noexcept
        {
            return std::forward<T>(arg);
        }
    };
}

template <typename ForwardIt, typename Sentinel, typename OutputIt, typename Value,
          typename BinaryOp = std::plus<>, typename Proj = util::identity>
OutputIt subset_sums(ForwardIt first, Sentinel last, OutputIt dest,
                     Value init, BinaryOp bin = {}, Proj proj = {})
{
    if (first == last)
        return *dest++ = init;
    auto value = proj(*first++);
    dest = subset_sums(first, last, dest, init, bin, proj);
    return subset_sums(first, last, dest, bin(init, value), bin, proj);
}

template <typename ForwardIt, typename Sentinel, typename OutputIt>
OutputIt subset_sums(ForwardIt first, Sentinel last, OutputIt dest)
{
    using Value = typename std::iterator_traits<ForwardIt>::value_type;
    return subset_sums(first, last, dest, Value{});
}

The (first, last, dest) version is a separate overload because the calculation of the value type is a bit complicated and I don't want to clutter the general version.

Usage example

The original problem:

#include <iostream>
#include <iterator>
#include <vector>

using number_t = long long;

int main()
{
    std::vector<number_t> nums{3, 1, 4};
    subset_sums(nums.begin(), nums.end(),
                std::ostream_iterator<number_t>{std::cout, "\n"});
}

Output:

0
4
1
5
3
7
4
8

Same problem, but with products instead of sums:

#include <iostream>
#include <iterator>
#include <vector>

using number_t = long long;

int main()
{
    std::vector<number_t> nums{3, 1, 4};
    subset_sums(nums.begin(), nums.end(),
                std::ostream_iterator<number_t>{std::cout, "\n"},
                number_t{1}, std::multiplies<>{});
}

Output:

1
4
1
4
3
12
3
12

Possibly non-contiguous substrings in a string:

#include <iostream>
#include <iterator>
#include <string>

int main()
{
    std::string str = "review";
    subset_sums(str.begin(), str.end(),
                std::ostream_iterator<std::string>{std::cout, "\n"},
                std::string{});
}

Output: (the initial empty line is intentional)


w
e
ew
i
iw
ie
iew
v
vw
ve
vew
vi
viw
vie
view
e
ew
ee
eew
ei
eiw
eie
eiew
ev
evw
eve
evew
evi
eviw
evie
eview
r
rw
re
rew
ri
riw
rie
riew
rv
rvw
rve
rvew
rvi
rviw
rvie
rview
re
rew
ree
reew
rei
reiw
reie
reiew
rev
revw
reve
revew
revi
reviw
revie
review

I have also tested with std::forward_list to make sure that the algorithm works with forward iterators.

\$\endgroup\$
7
  • 1
    \$\begingroup\$ so that's what modern C++ looks like. very nice! :) the ordering that you're using (not included; included) has allowed you to simplify and streamline the code into just two straight recursive calls. (I used the flipped order purely because it sounded better, to me :)). the string-based powerset is impressive, too. although, it will require exponential number of allocations and deallocations, no? In C, to overcome that, I'd use a fixed-sized char array and have the recursive calls fill it up gradually with the letters, mutating the array cells... (again your ordering is better there) \$\endgroup\$
    – Will Ness
    Jul 27, 2019 at 8:38
  • \$\begingroup\$ @WillNess Yeah, I should probably overwrite the value in place instead of passing by value. You should write that as an answer :) \$\endgroup\$
    – L. F.
    Jul 27, 2019 at 8:41
  • \$\begingroup\$ (well, not only because it sounded better; I wanted to show the general structure of emulating a nondeterministic algorithm by nested loops enumeration) \$\endgroup\$
    – Will Ness
    Jul 27, 2019 at 8:41
  • \$\begingroup\$ modern C++ is not my strongest suit. :) \$\endgroup\$
    – Will Ness
    Jul 27, 2019 at 8:46
  • 1
    \$\begingroup\$ @WillNess With some tests, I noticed that Small String Optimization kicks in here, so no allocation and deallocation :) But unnecessarily copying everything around is definitely a problem. \$\endgroup\$
    – L. F.
    Jul 27, 2019 at 8:48

1 Answer 1

3
\$\begingroup\$

This is pretty slick modern C++. I like it.

The recursion depth (equal to the input length) is unlikely to become a problem before the exponential explosion does.

Naming the all the template types isn't strictly necessary, but I think that giving names to the types makes for clarity which isn't present in this alternative:

template <typename ForwardIt>
auto subset_sums(ForwardIt first, auto last, auto dest)

That said, if we're able to use C++20, we could be more specific than simply typename, and use Concepts to make the code more resilient against accidents. This also gives us a place to deduce the default Value type, removing the need for the overload (IMO):

template <typename BinaryOp = std::plus<>,
          typename Proj = util::identity,
          std::forward_iterator ForwardIt,
          std::sentinel_for<ForwardIt> Sentinel,
          typename InputValue = std::invoke_result_t<Proj, typename std::iterator_traits<ForwardIt>::value_type>,
          typename Value = InputValue,
          std::output_iterator<std::invoke_result_t<BinaryOp, Value, InputValue>> OutputIt>
OutputIt subset_sums(ForwardIt first, Sentinel last, OutputIt dest,
                     Value init = {}, BinaryOp bin = {}, Proj proj = {})
{
    if (first == last)
        return *dest++ = init;
    auto value = proj(*first++);
    dest = subset_sums(first, last, dest, init, bin, proj);
    return subset_sums(first, last, dest, bin(init, value), bin, proj);
}

I'd consider adding (or even substituting) a version that accepts a std::ranges::range instead of an iterator-sentinel pair.


There's a bug you're getting away with when using ostream iterator for output, but which bites when we try to store our results into a container instead. We can expose it like this:

#include <array>
#include <iostream>
#include <iterator>

int main()
{
    using number_t = long long;

    std::array<number_t, 3> nums{3, 1, 4};
    std::array<number_t, 60> results;
    auto it = subset_sums(nums.begin(), nums.end(), results.begin());
    it = subset_sums(nums.begin(), nums.end(), it,
                     number_t{1}, std::multiplies<>{});

    std::copy(results.begin(), it,
              std::ostream_iterator<number_t>{std::cout, "\n"});
}

The problem is

        return *dest++ = init;

For most container iterators, that expression yields a reference to a value_type object, not the iterator itself. And using post-increment means we're returning the wrong position. It's equivalent to

        return *dest = init;

This means we continually overwrite the same element, and return dest unmodified, thereby claiming we've written nothing. I suggest:

    if (first == last) {
        *dest++ = init;
        return dest;
    }

I think that's clearer than the cutesy braceless version:

    if (first == last)
        return *dest++ = init, dest;
\$\endgroup\$
2
  • 1
    \$\begingroup\$ That bug mercilessly exposed my lack of testing ;) \$\endgroup\$
    – L. F.
    Sep 19, 2022 at 21:07
  • 2
    \$\begingroup\$ I was initially confused how we could return *dest when it apparently had the wrong type. To be honest, your standard is generally so high, that I was overjoyed to actually found a weakness in a function you wrote! And that's exactly what review is for - finding new ways to stress a function is often easier for the reviewer than for the author. \$\endgroup\$ Sep 20, 2022 at 6:57

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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