Problem 201: Subsets with a Unique Sum

Project Euler Problem 201 Solution

EulerSolve provides an optimized solution for Project Euler Problem 201, Subsets with a Unique Sum, with C++, Python, Java, and a step-by-step mathematical explanation.

Problem Summary Let $A=\{1^2,2^2,\dots,100^2\}$. Among all 50-element subsets of $A$, some subset sums occur exactly once and others occur more than once. The task is to add precisely those sums that are realized by one and only one 50-element subset. Brute force is hopeless because the number of 50-subsets is $\binom{100}{50}$. The important observation is that the final answer does not depend on the exact multiplicity of a sum once that multiplicity reaches 2. We only need to know whether a sum is impossible, unique, or already non-unique. Mathematical Approach Write $v_i=i^2$. For each prefix $\{v_1,\dots,v_t\}$, each subset size $j$, and each sum $s$, let $C_t(j,s)$ be the number of $j$-element subsets of that prefix whose elements add up to $s$. Then the quantity required by the problem is $$\sum_{s: C_{100}(50,s)=1} s.$$ The whole solution comes from turning this exact counting function into a three-state dynamic program. Fixed-Size Subset Counts The ordinary 0/1 subset-sum recurrence with a cardinality dimension is $$C_t(j,s)=C_{t-1}(j,s)+C_{t-1}(j-1,s-v_t).$$ The first term skips the new square $v_t$; the second term uses it. The base condition is $$C_0(0,0)=1,$$ because the empty subset is the unique 0-element subset with sum 0, while every other state with $t=0$ is impossible....

Detailed mathematical approach

Problem Summary

For a set $A$ of numbers, $\operatorname{sum}(A)$ is the sum of its elements, and $U(A,k)$ is the set of those numbers that are the sum of exactly one $k$-element subset of $A$. In the example of the statement, $B=\{1,3,6,8,10,11\}$ has $20$ subsets with three elements. The sums $15$, $17$, $19$, $20$, $22$ and $24$ each occur twice and the other eight sums once, so

$$\begin{aligned}U(B,3)&=\{10,12,14,18,\\&\phantom{{}=\{}21,25,27,29\},\\ \operatorname{sum}(U(B,3))&=156.\end{aligned}$$

The task concerns the set $S=\{1^2,2^2,\dots,100^2\}$ of the first hundred squares. The statement gives the number of its $50$-element subsets, $\binom{100}{50}$, as 100891344545564193334812497256, and asks for $\operatorname{sum}(U(S,50))$: the sum of all integers that are the sum of exactly one $50$-element subset of $S$. ^[1]

The whole solution in one sentence: instead of listing the subsets, we add the squares one at a time and record, for every subset size up to $50$ and every possible sum, only whether no subset, one subset or at least two subsets have that size and sum, and finally add up the sums that exactly one $50$-element subset reaches.

Mathematical Approach

Sections 1–3 count subsets by size and sum and cut the counts off at $2$, Section 4 works the example of the statement by hand, Sections 5 and 6 describe the table of the programs, and Sections 7 and 8 locate the unique sums.

1. Many subsets, few sums

By the formula $1^2+2^2+\dots+n^2$${}=n(n+1)(2n+1)/6$ for the square pyramidal numbers, ^[2] the fifty smallest squares add up to $50\cdot51\cdot101/6=42925$, and all hundred squares to $100\cdot101\cdot201/6=338350$. Hence every $50$-element subset of $S$ has a sum between $42925$ and $338350-42925=295425$, the sum of the fifty largest squares. About $1.01\cdot10^{29}$ subsets share at most $252501$ possible sums, on average about $4.0\cdot10^{23}$ subsets per sum. Listing the subsets is out of the question, but a table indexed by the possible sums is small.

2. Counting subsets by size and sum

Write $x_t=t^2$, and let $C_t(j,s)$ be the number of $j$-element subsets of $\{x_1,\dots,x_t\}$ whose elements add up to $s$. The empty set is the only subset of the empty set, so $C_0(0,0)=1$, and $C_0(j,s)=0$ for every other pair $(j,s)$. For $t\ge1$,

$$\begin{aligned}&C_t(j,s)=C_{t-1}(j,s)\\&\qquad{}+C_{t-1}(j-1,\,s-x_t),\end{aligned}$$

where the last term is $0$ when $j=0$ or $s\lt x_t$. Proof. A $j$-element subset of the first $t$ squares with sum $s$ either avoids $x_t$, and is then a $j$-element subset of the first $t-1$ squares with the same sum, or it contains $x_t$, and removing $x_t$ leaves a $(j-1)$-element subset of the first $t-1$ squares with sum $s-x_t$. Both correspondences are bijections; the second one is undone by putting $x_t$ back.

The task asks for the sum of all $s$ with $C_{100}(50,s)=1$. Computing $C_t$ from $C_{t-1}$ for $t=1,2,\dots,100$ is dynamic programming, which solves a large problem by building up the answers of smaller subproblems in a table. ^[3] It is the standard dynamic programming for the subset sum problem, extended by the size $j$. Its work is proportional to the number of possible sums, not to the number of subsets; such a bound is called pseudo-polynomial, because the sums can be exponentially larger than the number of digits needed to write the input. ^[4]

3. Three values are enough

We never need the counts themselves, only whether they are $0$, $1$ or at least $2$. So we clip every count at $2$, as in saturation arithmetic, where a result above the largest allowed value is replaced by that value. ^[5] Put $m(c)=\min(2,c)$. Claim. For all integers $a,b\ge0$,

$$m(a+b)=m\bigl(m(a)+m(b)\bigr).$$

Proof. If $a\ge2$ or $b\ge2$, then $a+b\ge2$ and $m(a)+m(b)\ge2$, so both sides equal $2$. Otherwise $m(a)=a$ and $m(b)=b$, and the two sides agree. Applied to the two terms of the recurrence of Section 2, the claim shows that the clipped counts $M_t(j,s)=m(C_t(j,s))$ satisfy the same recurrence with a clipping after each addition,

$$\begin{aligned}&M_t(j,s)=\min\bigl(2,\;M_{t-1}(j,s)\\&\qquad{}+M_{t-1}(j-1,\,s-x_t)\bigr),\end{aligned}$$

with the same initial values. By induction on $t$, this clipped recurrence computes exactly the values $M_t$, and the requested sum is the sum of all $s$ with $M_{100}(50,s)=1$. Without clipping the numbers would be large: the most frequent sums, $169173$ and $169177$, are each reached by 2649006171061158405975429 subsets, about $2.6\cdot10^{24}$. Such a count needs $82$ bits, more than a 64-bit integer holds, whereas a clipped count fits in one byte.

4. Worked example: the set of the statement

We run the clipped recurrence on $B$, adding $1,3,6,8,10,11$ in this order. For each size $j$, the row $j$ lists the sums $s$ with $M(j,s)\ne0$; all of them have the value $1$ unless the value $2$ is mentioned. Row $0$ always holds only the sum $0$. A new element $x$ adds to row $j$ the previous row $j-1$ shifted by $x$.

After $1$, $3$ and $6$: row $1$ is $1,3,6$, row $2$ is $4,7,9$ and row $3$ is $10$.
Adding $8$: row $2$ gains $1+8=9$, $3+8=11$ and $6+8=14$. The sum $9$ was already there as $3+6$, so it gets the value $2$. Row $3$ gains $4+8=12$, $7+8=15$ and $9+8=17$ and becomes $10,12,15,17$.
Adding $10$: row $3$ gains the previous row $2$ shifted by $10$, that is $14,17,19,21,24$. The sum $19$ inherits the value $2$ of $9$, because $1+8+10$ and $3+6+10$ both reach it, and $17$ gets the value $2$ because the new $1+6+10$ joins the old $3+6+8$. Row $2$ becomes $4,7,9,11,13,14,16,18$, with the value $2$ at $9$ and at $11=3+8=1+10$.
Adding $11$: row $3$ gains $15,18,20,22,24,25,27,29$, with the value $2$ at $20$ and $22$, inherited from $9$ and $11$. The sums $15$ and $24$ were already in row $3$, as $1+6+8$ and $6+8+10$, and arrive again as $1+3+11$ and $3+10+11$.

The final row $3$ has the value $2$ at $15,17,19,20,22,24$ and the value $1$ at $10,12,14,18,21,25,27,29$. The sums with value $1$ are exactly $U(B,3)$, and they add up to $156$, as in the statement. No count in this example exceeds $2$. Among the first eight squares, however, the sum $78$ has three $4$-element subsets, $1+4+9+64$, $1+16+25+36$ and $4+9+16+49$, and the clipped table stores $2$ for it, which still means "not unique".

5. One table, updated in place

The programs keep a single table $D[j][s]$ for $0\le j\le50$ instead of a new table for every $t$. When the square $x=x_t$ arrives, they run through the sizes $j$ downwards, from $\min(50,t)$ to $1$, and set

$$\begin{aligned}&D[j][s]\leftarrow\min\bigl(2,\;D[j][s]\\&\qquad{}+D[j-1][s-x]\bigr).\end{aligned}$$

The update of row $j$ must read row $j-1$ as it was before $x$ arrived, that is, $M_{t-1}(j-1,\cdot)$. Going downwards guarantees this, because row $j-1$ changes only after row $j$ is finished. Going upwards would break it: in the example, when $3$ arrives after $1$, the upward order first puts $3$ into row $1$ and then lets row $2$ read it, which records the sum $6=3+3$ of a "subset" that uses $3$ twice. For the same reason the one-array form of the 0–1 knapsack algorithm runs its capacity loop backwards. ^[6] Within one row the order of the sums does not matter, since the update reads row $j-1$ and writes row $j$; the programs happen to run $s$ downwards. Rows above $\min(50,t)$ are left alone: $t$ squares cannot form a subset with more than $t$ elements, and sizes above $50$ are never needed.

6. The window of possible sums

For every size $j$ the programs also keep two numbers $L_j$ and $H_j$. When $x$ is added, they scan row $j$ only for $L_{j-1}+x\le s\le H_{j-1}+x$, where $D[j-1][s-x]$ can be nonzero, and skip every $s$ with $D[j-1][s-x]=0$. Then $L_j$ becomes $\min(L_j,L_{j-1}+x)$ and $H_j$ becomes $\max(H_j,H_{j-1}+x)$, or simply $L_{j-1}+x$ and $H_{j-1}+x$ if row $j$ was empty.

Claim. After the first $t$ squares, for every $j\le\min(50,t)$, $L_j$ and $H_j$ are the smallest and the largest sum of $j$ of these squares; the rows with $j\gt t$ are still empty. Proof. The smallest sum of $j$ of the first $t$ squares either avoids $x_t$, and is then the old $L_j$, or it is $x_t$ plus the smallest sum of $j-1$ of the first $t-1$ squares, the old $L_{j-1}$. This is the recurrence of Section 2 with the sum of counts replaced by a minimum, and by a maximum for $H_j$; if row $j$ was empty, only the second case exists.

Because the squares increase, $L_j=x_1+\dots+x_j$, and $H_j$ is the sum of the $j$ largest squares so far. The largest possible $50$-element sum is $295425$, and a subset with fewer elements can be extended to $50$ elements by adding positive squares, so no row needs a larger sum: the table has $51$ rows of $295426$ entries, and the final scan of row $50$ runs from $42925$ to $295425$. Not every sum inside a window occurs: row $1$ holds only squares, and row $50$ has gaps (Section 8).

7. Complements and symmetry

The complement $S\setminus A$ of a $50$-element subset $A$ is again a $50$-element subset, and its sum is $338350-\operatorname{sum}(A)$. Taking the complement twice gives $A$ back, so complements match the $50$-element subsets with sum $s$ one-to-one with those with sum $338350-s$. The same matching between $k$-element and $(n-k)$-element subsets explains the symmetry $\binom nk=\binom n{n-k}$ of the binomial coefficients. ^[7] Hence $s$ is unique exactly when $338350-s$ is unique, and the map $s\mapsto338350-s$ sends $U(S,50)$ onto itself. Adding up $s$ over $U(S,50)$ therefore gives the same total as adding up $338350-s$, so twice the total is $338350\cdot|U(S,50)|$:

$$\begin{aligned}&\operatorname{sum}(U(S,50))\\&\qquad=169175\cdot|U(S,50)|.\end{aligned}$$

The example obeys the same rule, because $3$ is half of $6$: the elements of $B$ add up to $39$, the unique sums pair up as $10+29=12+27$${}=14+25=18+21=39$, and $156=4\cdot39$. The programs do not use this symmetry; it serves as a check below.

8. Where the unique sums lie

Every $50$-element subset arises from $\{1^2,\dots,50^2\}$ by exchanging some of these squares $a^2$ for squares $b^2$ with $b\ge51$, and each exchange raises the sum by $b^2-a^2\ge51^2-50^2=101$. So the sum $42925$ belongs only to the fifty smallest squares, and no sum between $42926$ and $43025$ occurs. The sum $43026$ is unique as well: two or more exchanges raise the sum by at least $101+(52^2-49^2)=404$, and a single exchange with $(b-a)(b+a)=101$, a prime, forces $b=51$ and $a=50$. The completed row $50$ shows that the smallest sum with two subsets is $43525=42925+600$; its two subsets come from exchanging $47^2$ for $53^2$, or $48^2$ and $49^2$ for $51^2$ and $52^2$:

$$\begin{aligned}&53^2-47^2=600\\&\qquad=(51^2+52^2)-(48^2+49^2).\end{aligned}$$

The completed row also shows that every unique sum lies within $2122$ of an end of the range, at most $45047$ or at least $293303$; in the middle the counts are huge (Section 3).

How the Code Works

The C++ program ^[8] starts in main with the defaults $n=100$ and choose $=50$, which parse_arguments lets --n= and --choose= change. Unless --skip-checkpoints is given, run_checkpoints demands solve(5, 3) $=330$: the ten $3$-element subsets of $\{1,4,9,16,25\}$ have different sums, and each square lies in $\binom42=6$ of them, so the sums add up to $6\cdot55=330$. Then main prints solve(n, choose). Sizes and sums are computed in int without overflow checks, which is safe for the defaults, but with --n=348 --choose=174 the product (choose + 1) * width already exceeds the int range.

solve builds values $=1,4,\dots,n^2$ and sets max_sum to the sum of the last choose values, the largest possible sum, and width to max_sum + 1. The table dp is one zero-filled std::vector<std::uint8_t> with (choose + 1) * width entries, in which the lambda idx puts the entry $(k,s)$ at position $k\cdot w+s$, with $w$ the width. dp[idx(0, 0)] = 1 is $C_0(0,0)=1$, and the vectors low and high hold $L_j$ and $H_j$, with high[k] = -1 for an empty row.

For the square x with index i, the main loop runs k from up = min(choose, i + 1) down to $1$ (Section 5), skips k when row $k-1$ is empty, and runs s from end $=H_{k-1}+x$ down to start $=L_{k-1}+x$ (Section 6). A zero entry add of row $k-1$ is skipped; otherwise the new entry is sum >= 2 ? 2 : sum, the clipping of Section 3. Then low[k] and high[k] are widened. Finally the sums $s$ from low[choose] to high[choose] with entry $1$ are added into the 64-bit integer answer. For choose $=0$ it skips the final scan and returns $0$, the sum of the empty set.

The Python program is a line-by-line transcription inside one function solve() with the fixed parameters $100$ and $50$, a zero-filled bytearray as table and positions k * width + s; it adds the total in a Python int, returns it as a string, and has no options and no checkpoint. The Java program does the same in main with a byte[] table. Java's byte is signed, from $-128$ to $127$; ^[9] entries are read as dp[...] & 0xFF, the usual unsigned conversion, which is harmless but not needed for the values $0$, $1$ and $2$, and stored as (byte) Math.min(v, 2); the row offsets basePrev and baseK are computed once per row, and the result is a long.

Complexity and Verification

For $n$ squares, subsets of size $1\le k\le n$ and largest sum $S_{\max}$, the table has $(k+1)(S_{\max}+1)$ entries and the scans take at most $nk(S_{\max}+1)$ steps: time $O(nkS_{\max})$ and memory $O(kS_{\max})$, the pseudo-polynomial bound of Section 2, which is polynomial here because $S_{\max}\le kn^2$. For $n=100$ and $k=50$ the table has $51\cdot295426=15\,066\,726$ one-byte entries, about 15 MB, and the bound $nk(S_{\max}+1)$ is $100\cdot50\cdot295426\approx1.48\cdot10^{9}$; the windows of Section 6 cut the inner loop down to $214\,816\,590$ steps, and in $97.3\%$ of them the entry read from row $k-1$ is nonzero, so the test for zero saves little. On an Apple M4 Max the C++ program, compiled with -O2, and the Java program need about $0.1$ and $0.16$ seconds, the Python program, which runs the same steps in the interpreter, about $16$ seconds. Rows that can no longer grow to $50$ elements are still updated; skipping them would save about half of the steps.

Besides the C++ checkpoint, we checked for this article, outside the published code:

a Python transcription of solve agrees, entry by entry in the final row, with a count over all subsets for every $n\le16$ and every size $k\le n$, and for $n=2k\le22$, with results such as $5100$ for $n=8$ and $152110$ for $n=20$;
the exact counts $C_{100}(j,s)$, computed with the recurrence of Section 2 modulo the primes $2^{61}-1$ and $2^{61}-31$, are determined by these residues through the Chinese remainder theorem, ^[10] since every count is at most $\binom{100}{j}\lt2^{100}$, below the product of the primes; after clipping at $2$ they agree with the table of the transcription in all $51$ rows, and the counts for $j=50$ add up to $\binom{100}{50}$ and are symmetric under $s\mapsto338350-s$;
the C++, Java and Python programs print the same number, and it is a multiple of $169175$, as Section 7 requires.

Footnotes and References

The references below supply the background facts used above. The clipped recurrence, the window bounds, the symmetry of the unique sums and all counts are derived or computed in this article.

Project Euler 201 — Subsets with a Unique Sum. The official statement defines U(A, k), works out sum(U(B, 3)) = 156 for B = {1, 3, 6, 8, 10, 11} and asks for sum(U(S, 50)) for S = {1², 2², …, 100²}.
Wikipedia — Square pyramidal number. The sum of the first n squares is n(n + 1)(2n + 1)/6.
Wikipedia — Dynamic programming. It breaks a problem down into simpler subproblems and, bottom-up, builds larger solutions from the stored solutions of smaller ones.
Wikipedia — Subset sum problem. Its dynamic programming tracks the pairs (i, s) such that some subset of the first i elements has the sum s, in time proportional to the number of elements times the range of possible sums; this is pseudo-polynomial, since that range need not be polynomial in the length of the input.
Wikipedia — Saturation arithmetic. Operations are limited to a fixed range, and a result greater than the maximum is set to the maximum.
cp-algorithms — Knapsack Problem. In the one-array form of the 0–1 knapsack algorithm the capacity loop runs in decreasing order, so that every value read still belongs to the previous item and each item is taken at most once.
Wikipedia — Binomial coefficient. C(n, k) is the number of k-element subsets of an n-element set, and C(n, k) = C(n, n − k) for 0 ≤ k ≤ n.
C++ — Euler201.cpp. The linked immutable revision contains parse_arguments, solve and run_checkpoints; it is the implementation record for this article.
Java Language Specification — §4.2.1 Integral Types and Values. The values of byte are the integers from −128 to 127. Python — bytearray: a mutable sequence of integers from 0 to 255; bytearray(n) is zero-filled.
Wikipedia — Chinese remainder theorem. For pairwise coprime moduli the remainders determine exactly one integer from 0 to the product of the moduli minus 1.

Problem 201 source code

C++

#include <algorithm>
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>

namespace {

using i64 = std::int64_t;

struct Options {
    int n = 100;
    int choose = 50;
    bool run_checkpoints = true;
};

bool parse_int_after_prefix(const std::string& arg, const std::string& prefix, int& value) {
    if (arg.rfind(prefix, 0U) != 0U) {
        return false;
    }
    const std::string tail = arg.substr(prefix.size());
    if (tail.empty()) {
        return false;
    }

    int parsed = 0;
    for (char c : tail) {
        if (c < '0' || c > '9') {
            return false;
        }
        parsed = parsed * 10 + static_cast<int>(c - '0');
    }
    value = parsed;
    return true;
}

bool parse_arguments(int argc, char** argv, Options& options) {
    for (int i = 1; i < argc; ++i) {
        const std::string arg(argv[i]);

        if (arg == "--skip-checkpoints") {
            options.run_checkpoints = false;
            continue;
        }
        if (parse_int_after_prefix(arg, "--n=", options.n) ||
            parse_int_after_prefix(arg, "--choose=", options.choose)) {
            continue;
        }

        std::cerr << "Unknown argument: " << arg << '\n';
        return false;
    }

    return options.n >= 1 && options.choose >= 0 && options.choose <= options.n;
}

i64 solve(const int n, const int choose) {
    std::vector<int> values;
    values.reserve(static_cast<std::size_t>(n));
    for (int i = 1; i <= n; ++i) {
        values.push_back(i * i);
    }

    int max_sum = 0;
    for (int i = n - choose; i < n; ++i) {
        if (i >= 0) {
            max_sum += values[static_cast<std::size_t>(i)];
        }
    }

    const int width = max_sum + 1;
    std::vector<std::uint8_t> dp(static_cast<std::size_t>((choose + 1) * width), 0);

    auto idx = [&](const int k, const int sum) -> std::size_t {
        return static_cast<std::size_t>(k) * static_cast<std::size_t>(width) +
               static_cast<std::size_t>(sum);
    };

    dp[idx(0, 0)] = 1;

    std::vector<int> low(choose + 1, 0);
    std::vector<int> high(choose + 1, -1);
    high[0] = 0;

    for (int i = 0; i < n; ++i) {
        const int x = values[static_cast<std::size_t>(i)];
        const int up = std::min(choose, i + 1);

        for (int k = up; k >= 1; --k) {
            if (high[k - 1] < 0) {
                continue;
            }

            const int start = low[k - 1] + x;
            const int end = high[k - 1] + x;

            for (int s = end; s >= start; --s) {
                const std::uint8_t add = dp[idx(k - 1, s - x)];
                if (add == 0) {
                    continue;
                }

                const std::size_t p = idx(k, s);
                const int sum = static_cast<int>(dp[p]) + static_cast<int>(add);
                dp[p] = static_cast<std::uint8_t>(sum >= 2 ? 2 : sum);
            }

            if (high[k] < 0) {
                low[k] = start;
                high[k] = end;
            } else {
                low[k] = std::min(low[k], start);
                high[k] = std::max(high[k], end);
            }
        }
    }

    i64 answer = 0;
    if (choose == 0) {
        return 0;
    }
    for (int s = low[choose]; s <= high[choose]; ++s) {
        if (dp[idx(choose, s)] == 1) {
            answer += s;
        }
    }
    return answer;
}

bool run_checkpoints() {
    if (solve(5, 3) != 330LL) {
        std::cerr << "Checkpoint failed for n=5,choose=3" << '\n';
        return false;
    }
    return true;
}

}  // namespace

int main(int argc, char** argv) {
    Options options;
    if (!parse_arguments(argc, argv, options)) {
        return 1;
    }
    if (options.run_checkpoints && !run_checkpoints()) {
        return 2;
    }

    std::cout << solve(options.n, options.choose) << '\n';
    return 0;
}

Python

def solve():
    n = 100
    choose = 50
    values = [i * i for i in range(1, n + 1)]

    max_sum = sum(values[n - choose:])
    width = max_sum + 1

    dp = bytearray((choose + 1) * width)
    dp[0] = 1

    low = [0] * (choose + 1)
    high = [-1] * (choose + 1)
    high[0] = 0

    for i in range(n):
        x = values[i]
        up = min(choose, i + 1)
        for k in range(up, 0, -1):
            if high[k - 1] < 0:
                continue
            start = low[k - 1] + x
            end = high[k - 1] + x
            for s in range(end, start - 1, -1):
                add = dp[(k - 1) * width + (s - x)]
                if add == 0:
                    continue
                p = k * width + s
                total = dp[p] + add
                dp[p] = 2 if total >= 2 else total
            if high[k] < 0:
                low[k] = start
                high[k] = end
            else:
                low[k] = min(low[k], start)
                high[k] = max(high[k], end)

    answer = 0
    for s in range(low[choose], high[choose] + 1):
        if dp[choose * width + s] == 1:
            answer += s
    return str(answer)

if __name__ == '__main__':
    print(solve())

Java

public class Euler201 {
    public static void main(String[] args) {
        int n = 100, choose = 50;
        int[] values = new int[n];
        for (int i = 0; i < n; i++)
            values[i] = (i + 1) * (i + 1);
        int maxSum = 0;
        for (int i = n - choose; i < n; i++)
            maxSum += values[i];
        int width = maxSum + 1;
        byte[] dp = new byte[(choose + 1) * width];
        dp[0] = 1;
        int[] low = new int[choose + 1], high = new int[choose + 1];
        java.util.Arrays.fill(high, -1);
        high[0] = 0;
        for (int i = 0; i < n; i++) {
            int x = values[i];
            int up = Math.min(choose, i + 1);
            for (int k = up; k >= 1; k--) {
                if (high[k - 1] < 0)
                    continue;
                int start = low[k - 1] + x, end = high[k - 1] + x;
                int basePrev = (k - 1) * width, baseK = k * width;
                for (int s = end; s >= start; s--) {
                    int add = dp[basePrev + s - x] & 0xFF;
                    if (add == 0)
                        continue;
                    int v = (dp[baseK + s] & 0xFF) + add;
                    dp[baseK + s] = (byte) Math.min(v, 2);
                }
                if (high[k] < 0) {
                    low[k] = start;
                    high[k] = end;
                } else {
                    low[k] = Math.min(low[k], start);
                    high[k] = Math.max(high[k], end);
                }
            }
        }
        long ans = 0;
        int base = choose * width;
        for (int s = low[choose]; s <= high[choose]; s++)
            if ((dp[base + s] & 0xFF) == 1)
                ans += s;
        System.out.println(ans);
    }
}