OR Convolution for Common People

#	User	Rating
1	tourist	3751
2	Benq	3727
3	cnnfls_csy	3691
4	Radewoosh	3651
5	jiangly	3632
6	orzdevinwang	3559
7	-0.5	3545
8	inaFSTream	3478
9	fantasy	3468
10	Rebelz	3415

#	User	Contrib.
1	adamant	178
2	awoo	167
3	BledDest	165
4	Um_nik	164
5	maroonrk	163
6	SecondThread	160
7	nor	158
8	-is-this-fft-	154
9	kostka	146
10	Geothermal	144

Several years ago, a wise person told me that a convolution on a bitwise operator is possible: Given $$$A, B$$$ of size $$$2^N$$$, you can compute

$$$C[i] = \sum_{j \oplus k = i} A[j] B[k]$$$

$$$C[i] = \sum_{j \land k = i} A[j] B[k]$$$

$$$C[i] = \sum_{j \lor k = i} A[j] B[k]$$$

in $$$O(2^N N)$$$ time. Cool!

I asked a wise person, how such things are possible. A wise person replied, "Of course you know how FFT works, let's begin with Fast Welsh-Hadamard Transform..." I said, No. I don't know how FFT works. Thank you. Then I just threw it into my ICPC teamnote.

Years have passed, I still don't know how FFT works, and while writing some stupid essay, a random idea came to my mind. I wondered, "Does nobody really know this? Why anyone didn't explain OR convolution this way?". I searched on Google, and nobody was telling things this way, so this is certainly not a common explanation. But why? It should be. Let me use my time to change things for good.

Sum of Subsets

For convenience, I'll use a set notation. We want to compute:

$$$C[i] = \sum_{j \cup k = i} A[j] B[k]$$$

If we can do this, we can also do $$$j \cap k$$$ easily. My approach can't do XOR convolution anyway, let's skip it.

Let's relax the condition as follows: $$$C^\prime[i] = \sum_{(j \cup k) \subseteq i} A[j] B[k]$$$

Which is $$$C^\prime[i] = \sum_{(j \subseteq i) \land (k \subseteq i)} A[j] B[k] = (\sum_{j \subseteq i} A[j]) (\sum_{k \subseteq i} B[k])$$$

Given an array $$$A$$$, how to compute $$$(\sum_{j \subseteq i} A[j])$$$? This is just a sum-of-subsets DP. Let's do it for both arrays $$$A$$$, $$$B$$$. Code:

// compute sum-of-subset
for (int i = 0; i < n; i++) {
  for (int j = 0; j < (1 << n); j++) {
    if ((j >> i) & 1) {
      A[j] += A[j - (1 << i)];
      B[j] += B[j - (1 << i)];
    }
  }
}

Then we have $$$C^\prime[i] = A[i] \times B[i]$$$.

A naughty cat

You have $$$C^\prime[i] = \sum_{j \subseteq i} C[j]$$$. How to get $$$C$$$ from $$$C^\prime$$$?

Think about this. You had an array $$$A$$$, but a naughty cat took a sum-of-subset of it and replaced it. You want to take $$$A$$$ back. What should you do? Just undo it!

for (int i = n - 1; i >= 0; i--) {
  for (int j = (1 << n) - 1; j >= 0; j--) {
    if ((j >> i) & 1) {
      A[j] -= A[j - (1 << i)];
    }
  }
}

You know what's going on, you are doing everything in reverse.

But $$$C^\prime$$$ is a sum-of-subset of $$$C$$$. What?

// compute C^\prime
for (int i = 0; i < (1 << n); i++) {
  C[i] = A[i] * B[i];
}

// reverse sum-of-subset
for (int i = n - 1; i >= 0; i--) {
  for (int j = (1 << n) - 1; j >= 0; j--) {
    if ((j >> i) & 1) {
      C[j] -= C[j - (1 << i)];
    }
  }
}

That's it, enjoy your convolution without some crazy ad-hoc maths!

Remark 1. This same approach works for GCD and LCM convolution since it's something like (num of primes $$$\leq n$$$)-dimension equivalent of the above approach, and "sum of divisors" can be done in $$$O(n \log n)$$$ time.

Remark 2. This article used 50 minutes of time that should be used to complete the stupid essay.

# Input: # Two (n-1)-degree polynomials A and B. # Integer n. # # Output: # C := A * B (mod x^n - 1) def circular_convolution(A, B, n): assert n == len(A) == len(B) A_eval = FFT(A) B_eval = FFT(B) C_eval = [Aw*Bw for Aw,Bw in zip(A_eval, B_eval)] C = IFFT(C_eval) return C

Comments (65)

Write comment?

ko_osaga

5 months ago, # |

+64

Wow, and this approach almost trivializes subset convolution. Now I can do subset convolution without any complicated tutorial :)

→ Reply

adamant

← Rev. 15 →

+58

I think it works in any lattice, that is a set with a $$$\leq$$$ relation (partially ordered set) with a "least common ancestor"

Unable to parse markup [type=CF_MATHJAX]

and a "highest common descendent"

. We can kind of interpret them as follows:

Unable to parse markup [type=CF_MATHJAX]
as the maximum element that is less or equal than both $$$i$$$ and $$$j$$$, i.e. similar to
Unable to parse markup [type=CF_MATHJAX]
,
Unable to parse markup [type=CF_MATHJAX]
or $$$i \cap j$$$,
Unable to parse markup [type=CF_MATHJAX]
as the minimum element that is greater or equal than both $$$i$$$ and $$$j$$$, i.e. similar to
Unable to parse markup [type=CF_MATHJAX]
,
Unable to parse markup [type=CF_MATHJAX]
or $$$i \cup j$$$.

In this notion, for $$$C[k]$$$ defined as

it always holds that

And you can always inverse the sum over

via Möbius inversion formula as

where

is the Möbius function of the poset. See also this article by nor which extensively goes into the topic from poset point of view.

I think, this approach is generally known to CP community, as there are problems about GCD/LCM convolutions on Library Checker, but maybe it's not standard to use it in tutorials because tutorial authors perceive polynomial evaluation/interpolation, or sometimes matrix Kronecker product as more natural, insightful and relatable to cpers than the poset point of view?

Besides, these tutorials are usually written in a way that is supposed to be uniform for OR convolution, AND convolution and XOR convolution, and as you pointed it out yourself it doesn't work with XOR convolution.

5 months ago, # ^ |

+53

Lattice, such a cool name, thanks!

ecnerwala

+19

Here's a fun lattice: subspaces of

under inclusion. (This recently appeared as part of problem A on UCup 1 Stage 13: Iberia).

You can experimentally find the closed form of the Mobius function or derive it using some math.

Spoiler

Does anyone have a nice combinatorial interpretation of this? (Combinatorial means something like this comment for the lattice of partitions.)

maroonrk

+42

Let me try.

Let

. For a subspace $$$W \subset V$$$, the equation we ultimately want to have is

and $$$0$$$ otherwise. If we let

and

, the equation becomes

subspaces of

with dimension

. (BTW How did you use \mathbb{F} in math mode? It gave me an error...)

The case of $$$n=0$$$ is easy, so let's focus on

Take an arbitrary vector $$$v$$$, say,

. For a subspace of

, let's call it type A if it contains $$$v$$$ and type B otherwise. I will show that

type A subspaces of dimension

type B subspaces of dimension

, then everything calcels out in the sought sum.

Consider a type A subspace of dimension $$$k+1$$$ and let $$$b_i$$$ (

) be its basis. We can safely assume

. Then, for any

(

) form a basis and they correspond to a type B subspace of dimension $$$k$$$. Thus we have a

-to-one correspondence and this completes the proof.

Um_nik

Wow, did you upsolve it?

Yeah, it was a pretty cute problem, the math wasn't too bad. I wonder if it's possible to solve in subquadratic time, and I also wonder if it's possible without PIE (e.g. over floating point numbers).

From your comment it seems that you found it not that hard? Mind telling the gist of your solution? We have some digit dps with insane tricks.

← Rev. 3 →

+23

First, we'll do PIE on the basis condition: for each subpsace $$$B'$$$ of the given basis $$$B$$$, we want to count the number of subsets of

with all elements in $$$B'$$$, weighted by

The key observation is that, the problem on a subspace $$$S$$$ of dimension $$$M$$$ and an upper bound $$$X$$$ can be reduced to the problem on

with some upper bound of $$$X'$$$ (which clearly has

valid subsets).

The proof is not too difficult: consider the reduced-row-echelon-form basis $$$B$$$ of $$$S$$$, and express each element of $$$S$$$ in terms of this basis (i.e. as

for some

). One nice property of an RREF basis is that lexicographic ordering is preserved, i.e.

. Thus, the elements of $$$S$$$ less than $$$X$$$ must be the elements of

at most some upper bound $$$X'$$$.

We can give an explicit construction of $$$X'$$$: consider the element

of $$$S$$$ which matches $$$X$$$ for as many digits as possible. Then, if

, our upper bound is

; otherwise, our upper bound is

, where $$$d$$$ is the number of digits of $$$v$$$ after the mismatch.

To finish the problem, we do digit-DP on the RREF basis of the subspace $$$S$$$. We go from the least significant bit upwards, and our state is the current dimension, as well as whether we've hit the first mismatch of

with $$$X$$$ or not. For each digit, we either a vector starting at this digit to our basis, or we don't. It's helpful to note that, in the second case, exactly half of the bases will match $$$X$$$ at that digit.

It's kind of interesting that the problem statement gives you an explicit subspace; it's almost a hint that you should look at subspaces and try to reduce the problem. I think the solution would've been harder to come up with if the problem just asked for full-rank-subsets of

nor

+11

A little nitpick: you only need semilattices for such an argument to work.

One obvious case where this becomes significant is the case of trees — a tree forms a semilattice (but not a lattice) under the LCA operation, and you can find things like

where $$$x_i$$$ are some numbers assigned to vertices.

Looking at it from a poset perspective, the DP to recover $$$f$$$ from the zeta transform — which is the square of the subtree sum of that vertex — is just a more manageable way to compute the Möbius function via the theorem for lattices mentioned in my blog, and since the answer is linear in the Mobius function, it manages to also solve the problem.

← Rev. 2 →

Yea, sorry, I'm not a lattice expert and did not know the name semilattice >.<

Hyperbolic

+13

super straightforward approach, I love it.

Swistakk

+16

"Does nobody really know this?" — it's certainly the way I always thought about it and I didn't even know that it has any FWHT/FFT connections xd

+69

I still don't know what FWHT is...

This is literally the transform you do to the array for XOR convolution...

DeadlyPillow

-10

This looks amazing
Can you do non-binary base xor convolution, please mister legendary grandmaster?

Thanks! Maybe you are finding this?

Looks interesting, thank you.

scanhex

1103E - Radix sum may be relevant too. Is it what you are asking about in (2.)?

pajenegod

← Rev. 10 →

There is a super nice and general way to view all kinds of transforms that are used for different kinds of convolution. The trick is to think about properties (functions) $$$f$$$ such that

. In your example of OR-convolution, the proprties you are using are

Let's as another example take circular convolution with periodicity $$$n$$$. Meaning you are given two polynomials $$$A(x)$$$ and $$$B(x)$$$, and your goal is to find the polynomial

, which is an $$$(n-1)$$$-degree polynomial.

Note that for any complex number $$$\omega$$$ such that

, we have that

. There are $$$n$$$ such complex numbers, and $$$C$$$ is an $$$(n - 1)$$$-degree polynomial. This means that by evaluating $$$A$$$ and $$$B$$$ in all of the $$$\omega$$$:s we have enough information to calculate $$$C$$$ using interpolation. The properties "$$$f$$$" that we are using here is the evaluation of a polynomial at the $$$\omega$$$:s.

So what is FFT? If you give FFT a $$$(n-1)$$$-degree polynomial, then it evaluates the polynomial in all $$$n$$$-th roots of unity (the $$$\omega$$$:s). Inverse FFT is the reverse of this, it finds a $$$(n-1)$$$-degree polynomial using interpolation. So if you have FFT and IFFT implemented, then it is trivial to implement circular convolution.

Here is an example of a Python implemention of circular convolution using FFT.

+18

Sir, I think the point of this blog is specifically to avoid this general way to view them...

True (and this blog does a good job of explaining it in that way), but the DPs used for such transforms usually end up being representable as such maps. There's stuff like the infimal convolution that feels hard to explain in such a simplified manner, but is useful in a lot of places nevertheless (for example, in Alien's trick).

No, just using sensible terminology and approach.

But pajenegod uses the same approach as the blogs on fwht you complain about...

Yeah, glad that you know where it got wrong

If something has an established name, it's sensible to call it by the name, rather than explain it without mentioning the name...

Opposite of how I learned to write: Use the easiest way to describe things.

I mean, I think your posts have a specific audience, they probably know what's going on, so it's ok. I just found it sad that nobody discussed this for general audience (such as me).

I mean, I get your point. It's much worse in math textbooks and I hate it. But complaining that blog about something that is exactly FWHT (XOR convolution) mentions FWHT and FFT and skipping it because of this is still weird.

Considering that Um_nik don't know FWHT, nor I do, most schoolchildrens won't, and my 2400+ friends saying they are enlightened, I don't think this is a niche position.

Bruh, it's more like you and Um_nik know it, but refuse to acknowledge it by this name.

No I really don't know it. Really.. I kinda know FFT, but zero idea on FWHT.

I don't think that's always true. Do you know what "Kadane's algorithm" is?

It's the algorithm to find the max-sum segment. I constantly forget its details because prefix sums are more natural for this. I think, it still makes sense to mention its name in a tutorial about it, and it shouldn't divert people from reading the tutorial? Besides, I don't know a better name for it anyway.

That depends on people I think. The algorithm in this situation is so simple, that giving it a name (from my viewpoint) creates an unearned aura of scientific significance and/or complexity. I don't think that algorithm deserves a name, and I would prefer to refer to it by "max-sum subsegment".

The situation is a bit different with FWHT and XOR convolution. Here I just think that "XOR convolution in

" is the algorithm, and FWHT might be the name of the transform used in the algorithm, but mentioning it instead of XOR convolution for me seems like an obfuscation, like you are trying to hide XOR convolution and/or give it a scientific-sounding name.

And I have to acknowledge that my position is weird because I don't have anything against saying FFT instead of "polynomial multiplication in $$$O(n \log n)$$$.

+21

One day someone said he was using an "imos method" to do some stuff. I asked, what's that trick? And it was a difference array. I almost died. I don't know who "imos" is, but shame on him. I can say that. That's like a communication crashing because of some crazy ego.

Here's an even more obtuse example: you can use something called the Bird-Meerten's formalism to derive Kadane's algorithm from the $$$O(n^3)$$$ definition. Though it is definitely a cool thing when it comes to deriving programs formally from their specification (and I really like it for that reason), it's not really useful to learn in the context of CP.

I would say it is more useful to name ideas rather than to name specific algorithms (so stuff like posets etc. make more sense in this context, but FWHT in isolation does not).

Well yes, this blog is about doing OR-convolution using sum-of-subsets.

However I think that it is still good to point out that there are very similar explanations of how to do other convolutions. For example the blog just leaves out XOR-convolution claiming that "My approach can't do XOR convolution". Which is not entirely true.

The transform used for XOR-convolution is

The reason for how I know this is explained in my original comment. It has to do with the fact that

for

← Rev. 5 →

Does it have any natural explanation?

The one I know is to treat $$$A$$$ and $$$B$$$ as multivariate polynomials, where the entry with the index

corresponds to the coefficient near

for $$$(n+1)$$$ variables

, one per bit. We want them to behave like

where $$$i \oplus j$$$ is the XOR of $$$i$$$ and $$$j$$$. So, we evaluate them in numbers

such that

for each bit $$$k$$$. Conveniently it's equivalent to

, hence

, so the transform for the XOR convolution is equivalent to evaluating these multivariate polynomials in the vertices of the cube

ko_osaga, this (poly eval/interpolation interpretation) and the comment below (set theoretic interpretation) is essentially FWHT. Do you have any idea of it now? @_@

Ok, adamant eventually made me understand this weird math stuff. You win ;_;

I think I get that set theory 100%, but for the poly one I don't know how it corresponds to an algorithm. But I just want to chill, so plz don't explain it

I think, you just change

A[j] += A[j - (1 << i)];

tie(A[j - (1 << i)], A[j]) = make_pair(
  A[j - (1 << i)] + A[j],
  A[j - (1 << i)] - A[j]
);

In your impl of the OR transform, as OR transform is eval in

+24

Here is how I would intuitively explain the transforms of many different types of convolutions.

OR-convolution

uses the transform

(called sum-of-subsets transform)

since

AND-convolution

XOR-convolution

(called FWHT)

Circular convolution mod $$$n$$$

(called FFT)

GCD-convolution

LCM-convolution

Oh, I see. Yeah, looking on it this way makes a lot of sense. The family of transforms for XOR convolution still looks arbitrary and somewhat unmotivated, but it's still a very nice way to present it.

+10

I suppose, from set-theoretic point of view you define it as

and then

which then rewrites as

which explains the formula. But there's no way I would ever consider such transform naturally... Like, I don't see a meaningful relaxation of $$$i \Delta j = k$$$ similar to how the blog goes from $$$i \cup j = k$$$ to

P.S.

is the symmetric difference if $$$i$$$ and $$$j$$$.

This is clean, good!

We need $$$n = 2^k$$$ to have an $$$O(n \log n)$$$ algorithm, right?

Standard FFT needs it, but you can reduce arbitrary $$$n$$$ to a convolution (which is doable with powers of $$$2$$$) with chirp Z-transform. On the other hand, if you only want to compute

, rather than

for each root of

, you can as well compute

in full and reduce it modulo $$$x^n-1$$$ in $$$O(n)$$$.

Essentially yes.

However, there is a common trick to get around this limitation. By paying a factor of 2 extra, you can use circular convolution to calculate usual convolution (no modding by $$$(x^n - 1)$$$). This is because modding with $$$(x^n - 1)$$$ doesn't matter if $$$n$$$ becomes large enough.

So to do circular convolution for an $$$n$$$ that is not a power of 2, you start by doing a circular convolution with a large power of 2 as its periodicity. Then you simply mod the result of that by $$$x^n - 1$$$.

Modding by $$$x^n$$$ is removing all coefficients with index $$$\geq n$$$. You want to mod by $$$x^n-1$$$, that is substitute

and turn

into $$$x^b$$$. Note that you can't do this if you want to invert the circular convolution (e.g. in 901E - Cyclic Cipher).

Ah ops, meant

and not

. Thanks for pointing that out. I'll fix it.

CLUMSY_BOT

+14

What for uncommon people like us?

-11

Thanks for the easy to understand blog — it is clearly another step in the right direction since it provides more evidence for the claim that all problems can be solved using DP.

Golovanov399

You may also consider what you did (specifically sum-of-subset) as if you calculated the following DP: dp[b][i] is sum of $$$f(j)$$$ over all $$$j$$$ so that $$$j$$$ is a subset of $$$i$$$ and may differ only in the last (or first, doesn't matter) $$$b$$$ bits. Do you know how to calculate dp[b][i] from dp[b - 1][*]? Yes, if the $$$b$$$-th bit of $$$i$$$ is zero, then these values coincide, otherwise dp[b][i] = dp[b - 1][i] + dp[b - 1][i - (1 << b)]. Your two-cycles is computing this dp on one layer.

Keeping this in mind, you may generalize this to xor-convolution. Indeed, let dp[b][i] be the sum of $$$f(j)$$$ over $$$j$$$ that only differ from $$$i$$$ in the last $$$b$$$ bits, but also each $$$f(j)$$$ is multiplied by $$$-1$$$ if the number of bits they differ in is odd. Now I think you also know how to compute dp[b][i] from dp[b - 1][*].

Idk if this makes any visual sense to you, but probably it is easier to understand xor-convolution in terms of dp

BadalArya

-32

Number of legend's comment in this blog >>>>>>>>>>>

jjang36524

-76

Do not read this article if you are not red. Go solve binary search instead.

Perpetually_Purple

Was funny before 1000000007th time.

+48

It's not funny and the post is not exclusively for 2400+. If you understand SOS DP you can read it.

Botswana

-25

keep it up. do nto lsten to ahders. yuo aer fnuonny.

-Yuor Snciernly Btsowana

luanmenglei

-8

Wow FMT&FWT!

camc

Cool! I used this technique to solve these problems:

You'll have to join this group for the second one.

Thank you for writing such a clear and concise blog.

5 weeks ago, # ^ |

-26

What!? no upvotes...

AkibAzmain

What is this set notation in your summation ($$$\sum$$$) notation? Apologies if the question is duplicate or too noob.

The number $$$j, k$$$ is not a set per se, but I'm considering it as a set, which makes sense if you consider the bitmask.

spookywooky

Can somebody explain how to read/understand that formular: $$$C[i] = \sum_{j \cup k = i} A[j] B[k]$$$

If A={1,2,3} and B={4,5,6}, what would C[] be? Has A[] and B[] same size?

vgtcross

Using bitwise operations, the formula is $$$C[i] = \displaystyle\sum_{j | k = i}A[j]B[k]$$$.

The formula tells us that for all $$$0 \le i < 2^N$$$, $$$C[i]$$$ is the sum of $$$A[j]B[k]$$$ over all pairs $$$(j, k)$$$ such that $$$0 \le j, k < 2^N$$$ and $$$j | k = i$$$.

The first line of the blog says ... Given $$$A$$$, $$$B$$$ of size $$$2^N$$$.... Your arrays $$$A$$$ and $$$B$$$ are not of size $$$2^N$$$. But let's suppose that $$$N = 2$$$ and $$$A = [1, 2, 3, 4]$$$ and $$$B = [5, 6, 7, 8]$$$.

Now, we go through all pairs $$$(j, k)$$$ such that $$$0 \le j, k < 2^N$$$ or in this case, $$$0 \le j, k < 4$$$. We will calculate the bitwise OR of each of these pairs.

Bitwise OR of all pairs

We can group them like this:

Bitwise OR is 0: $$$(0, 0)$$$
Bitwise OR is 1: $$$(0, 1)$$$, $$$(1, 0)$$$, $$$(1, 1)$$$
Bitwise OR is 2: $$$(0, 2)$$$, $$$(2, 0)$$$, $$$(2, 2)$$$
Bitwise OR is 3: $$$(0, 3)$$$, $$$(1, 2)$$$, $$$(1, 3)$$$, $$$(2, 1)$$$, $$$(2, 3)$$$, $$$(3, 0)$$$, $$$(3, 1)$$$, $$$(3, 2)$$$, $$$(3, 3)$$$

Thus,

$$$C[0] = A[0]B[0] = 1 \cdot 5 = 5$$$

$$$C[1] = A[0]B[1] + A[1]B[0] + A[1]B[1]$$$

$$$C[1] = 1 \cdot 6 + 2 \cdot 5 + 2 \cdot 6$$$

$$$C[1] = 6 + 10 + 12 = 28$$$

$$$C[2] = A[0]B[2] + A[2]B[0] + A[2]B[2]$$$

$$$C[2] = 1 \cdot 7 + 3 \cdot 5 + 3 \cdot 7$$$

$$$C[2] = 7 + 15 + 21 = 43$$$

$$$C[3] = A[0]B[3] + A[1]B[2] + A[1]B[3] + A[2]B[1] + A[2]B[3] + A[3]B[0] + A[3]B[1] + A[3]B[2] + A[3]B[3]$$$

$$$C[3] = 1 \cdot 8 + 2 \cdot 7 + 2 \cdot 8 + 3 \cdot 6 + 3 \cdot 8 + 4 \cdot 5 + 4 \cdot 6 + 4 \cdot 7 + 4 \cdot 8$$$

$$$C[3] = 8 + 14 + 16 + 18 + 24 + 20 + 24 + 28 + 32 = 184$$$

This means that $$$C = [5, 28, 43, 184]$$$.

You can check that this is correct using the code in the blog.

Code

#include <bits/stdc++.h>

using namespace std;

int main() {
    int n = 2;
    int A[1 << n];
    int B[1 << n];
    int C[1 << n];
    
    for (int i = 0; i < (1 << n); i++) {
        cin >> A[i];
    }
    
    for (int i = 0; i < (1 << n); i++) {
        cin >> B[i];
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < (1 << n); j++) {
            if ((j >> i) & 1) {
                A[j] += A[j - (1 << i)];
                B[j] += B[j - (1 << i)];
            }
        }
    }
    
    for (int i = 0; i < (1 << n); i++) {
        C[i] = A[i] * B[i];
    }
    
    for (int i = n - 1; i >= 0; i--) {
        for (int j = (1 << n) - 1; j >= 0; j--) {
            if ((j >> i) & 1) {
                C[j] -= C[j - (1 << i)];
            }
        }
    }
    
    for (int i = 0; i < (1 << n); i++) {
        cout << C[i] << ' ';
    }
    
    cout << '\n';
    
    return 0;
}

Results

Input:
1 2 3 4
5 6 7 8

Output:
5 28 43 184

Thanks a lot!

ko_osaga's blog

Sum of Subsets

A naughty cat