Problem

Let's look at the following two problems:
1. Given an array $$$A$$$ of $$$N$$$ elements where $$$0 \le A_i \le X$$$ for some positive integer $$$X$$$, find all possible subset sums.
2. Given an array $$$A$$$ of $$$N$$$ elements where $$$0 \le A_i \le X$$$ for some positive integer $$$X$$$, for all possible subset sums, calculate the minimum number of elements required to achieve that sum.

Thanks to socho for improving the tutorial!

Solution

This is a classical dynamic programming problem which can be solved in $$$O(N^2 \times X)$$$ (the sum of elements is bounded by $$$N \times X$$$) and hence that solution won't be discussed in much detail here. We can create an array $$$\it{dp}$$$ of size $$$X + 1$$$ and say that $$$\it{dp}_a$$$ is $$$1$$$ if it's possible to form a sum of $$$a$$$ using some elements from the array and $$$0$$$ otherwise. Then, we try to include every element $$$A_i$$$ and set all $$$\it{dp}_a$$$ for which $$$\it{dp}_{a - A_i}$$$ is $$$1$$$, to $$$1$$$.

However, if the sum of elements is bounded by $$$N$$$, it turns out that this problem can be solved in $$$O(N\sqrt{N})$$$. Formally, we have the following constraint:

So, what is the maximum number of distinct elements our array can have if its sum is bounded by $$$N$$$? Since we are trying to maximise, it is optimal for us to consider the smallest possible elements, starting from $$$1$$$. We want to find the smallest $$$P$$$ such that the sum of the first $$$P$$$ natural numbers is equal to $$$N$$$. The sum of the first $$$N$$$ natural numbers is given by the formula $$$\frac{P (P + 1)}{2}$$$. Solving $$$\frac{P (P + 1)}{2} = N$$$ for $$$P$$$, we get:

It's okay for $$$P$$$ to be slightly bigger, as we want a rough estimate only.

Therefore, we have at most $$$\sqrt{2N}$$$ distinct values in the array, which allows us to develop an $$$O(N\sqrt{N})$$$ algorithm.

Let's retain the definition of $$$\it{dp}$$$. Our transitions will change. We can process elements in pairs of $$$(W_i, K_i)$$$ where $$$W_i$$$ and $$$K_i$$$ correspond to the value and frequency of element i of the compressed array. How do we update the $$$\it{dp}$$$ array? To understand this, first take a look at what an array looks like if the $$$i^{\it{th}}$$$ element is $$$i \mathbin{\%} W_i$$$. Consider $$$W_i = 4$$$.

So, for each $$$W_i$$$, let $$$T$$$ be any value smaller than $$$W_i$$$ and greater than or equal to $$$0$$$ $$$(0 \le T \le W_i - 1)$$$. We see that array indices with the same value of $$$T$$$ are exactly $$$W_i$$$ elements apart. Let's consider indices with the same value of $$$T$$$ together. Let's set $$$T = 1$$$ and look at the indices where $$$T = 1$$$ appears in the array above. Call this array $$$B$$$.

Recall that the $$$i^{\it{th}}$$$ index of the $$$\it{dp}$$$ array stores whether we can form a sum of $$$i$$$. Since the same $$$T$$$ values occur $$$W_i$$$ elements apart, going from one occurrence of $$$T$$$ to the next uses a single copy of $$$W_i$$$. Since we have exactly $$$K_i$$$ copies of $$$W_i$$$, we can form sum $$$i$$$ if $$$\it{dp}_{i - W_i \times Y}$$$ for some $$$Y$$$ $$$(0 \le Y \le K_i)$$$ is one. In other words, if the sum of all such $$$\it{dp}$$$ values is positive, then $$$\it{dp}_i$$$ is possible. We can maintain a variable which stores the sum of the last $$$K_i$$$ such $$$\it{dp}$$$ values. For example, for the ninth index, if we have at least two copies of $$$W_i = 4$$$, then we want at least one of $$$dp_5$$$ or $$$dp_1$$$ to be $$$1$$$.

For every $$$W_i$$$, for every index $$$P$$$ in the range $$$[0, W_i - 1]$$$, we loop over all multiples of $$$W_i$$$ starting at $$$P$$$. That is a total of $$$\frac{N}{W_i}$$$ multiples per $$$P$$$. Since $$$P$$$ assumes exactly $$$W_i$$$ different values, the complexity for doing so is $$$O(W_i \times \frac{N}{W_i})$$$. Since we do this $$$\sqrt{2N}$$$ times, the final complexity is $$$O(\sqrt{N} \times W_i \times \frac{N}{W_i}) = O(N\sqrt{N})$$$. We require $$$O(N)$$$ memory. Take a look at the code below to understand this better.

#include <bits/stdc++.h>

using namespace std;

int main() {
    int N;
    cin >> N;

    // Sum of elements <= N implies that every element is <= N
    vector<int> freq(N + 1, 0);
    for (int i = 0; i < N; i++) {
        int x;
        cin >> x;

        freq[x]++;
    }

    vector<pair<int, int>> compressed;
    for (int i = 1; i <= N; i++) {
        if (freq[i] > 0) compressed.emplace_back(i, freq[i]);
    }

    vector<int> dp(N + 1, 0);
    dp[0] = 1;

    for (const auto &[w, k] : compressed) {
        vector<int> ndp = dp;

        for (int p = 0; p < w; p++) {
            int sum = 0;

            for (int multiple = p, count = 0; multiple <= N; multiple += w, count++) {
                if (count > k) {
                    sum -= dp[multiple - w * count];
                    count--;
                }
                
                if (sum > 0) ndp[multiple] = 1;
                sum += dp[multiple];
            }
        }

        swap(dp, ndp);
    }

    cout << "Possible subset sums are:\n";
    for (int i = 0; i <= N; i++) {
        if (dp[i] > 0) cout << i << " ";
    }
}

This successfully solves the first problem mentioned at the starting of the post. Let's now take a look at how to modify our approach to solve the second one as well. Before proceeding, make sure you understand the tutorial till this point. If you want to try the second problem once yourself, you may do so here: 95E - Lucky Country. Here's my code for it: 137173086.

This time, we want to find the minimum number of elements in a subset, for each subset sum. $$$\it{dp}_i$$$ should now store the minimum number of elements required to form a subset sum of $$$i$$$. $$$\it{dp}_i = \infty$$$ if it is impossible to do so. How do we transition between states? This time, it is optimal to take the minimum among the last $$$K_i$$$ $$$\it{dp}$$$ values (remember that the last $$$K_i$$$ values refers to the last $$$K_i$$$ indices with value $$$T$$$ as shown for the first problem i.e. array $$$B$$$). We can do so by maintaining the minimum over the last $$$K_i$$$ $$$\it{dp}$$$ values with indices belonging to array $$$B$$$. This essentially becomes a sliding window minimum problem, and the time complexity remains the same. At this point, you might be wondering what value to push inside the deque so that we can accurately find the minimum since we are iterating over multiples. Let $$$L$$$ we the number of times we have added $$$W_i$$$ to $$$P$$$. We can simply insert $$$\it{dp}_{B_j} - L$$$. Once we have the minimum, we add a constant value, which is the current value of $$$L$$$. This is the same idea used to solve the problem Lucky Countries mentioned above. Take a look at the code snippet below.

vector<int> dp(N + 1, INF);
dp[0] = 0;

for (const auto &[w, k] : components) {
    vector<int> ndp = dp;
    for (int i = 0; i < w; i++) {   
        deque<pair<int, int>> window;

        for (int j = i, mul = 0; j <= N; j += w, mul++) {
            while (!window.empty() && window.front().second < mul - k)
                window.pop_front();

            if (!window.empty()) smin(ndp[j], window.front().first + mul);

            while (!window.empty() && window.back().first >= dp[j] - mul)
                window.pop_back();
            
            window.emplace_back(dp[j] - mul, mul);
        }
    }

    swap(ndp, dp);
}

Check out my YouTube channel Algorithms Conquered to learn many more interesting algorithms!