Overview

Given \(N \le 40\) items, count the number of ways to select some items so that the total is exactly \(S\). A brute-force search of \(2^N\) is too large, so we solve this using “Meet-in-the-Middle” by splitting the items in half.

Analysis

Each candy has two choices: “buy / don’t buy,” so naively we could examine all subsets and count those whose sum equals \(S\). However, the complexity is \(2^N\), and when \(N=40\), this gives \(2^{40} \approx 10^{12}\) possibilities, which won’t finish in a reasonable time (TLE).

The key insight here is that “40 items is too many, but 20 items at a time can be fully enumerated.”
Split the \(N\) items into two groups (left and right), and create a list \(L\) of all subset sums from the left group and a list \(R\) of all subset sums from the right group. Then the answer is obtained by counting the number of pairs where “the left sum is \(x\) and the right sum is \(S-x\).”

For example, if \(S=10\), and there are \(c_1\) ways to make \(3\) yen from the left and \(c_2\) ways to make \(7\) yen from the right, then there are \(c_1 \times c_2\) combinations that total \(10\) yen.
Since different candies are distinct even if they have the same price, “duplicates in subset sums” must be correctly counted as separate ways.

Algorithm

1. Split the array \(A\) into the first half and the second half (left: \(n_1=\lfloor N/2 \rfloor\) items, right: \(N-n_1\) items).
2. For the left side, enumerate all subset sums and store them in array \(L\). Do the same for the right side to create \(R\).
   
   • Subset sums can be generated starting from \([0]\), and for each element \(a\), adding both “existing sum \(s\)” and “\(s+a\)” to produce \(2^k\) values.
3. Sort \(L\) and \(R\).
4. Use two pointers to count “the number of pairs where \(L[i] + R[j] = S\)” (move \(i\) from the smallest side and \(j\) from the largest side).
   • If \(L[i]+R[j]=S\), count how many consecutive identical values there are on each side (\(c_1, c_2\)), and add \(c_1 \times c_2\) to \(ans\) all at once.
   • If the sum is too small, advance the \(i\) pointer; if too large, move the \(j\) pointer back.
   • Consecutive identical values are grouped and skipped together to avoid unnecessary comparisons.

With this method, the brute-force \(2^{40}\) is reduced to enumeration of \(2^{20}\) scale + sorting + linear scan.

Complexity

Let \(n_1, n_2\) be the number of elements in the left and right groups respectively. Then \(|L|=2^{n_1}, |R|=2^{n_2}\). - Time complexity: \(O(2^{n_1} + 2^{n_2} + 2^{n_1}\log 2^{n_1} + 2^{n_2}\log 2^{n_2})\)
(dominated by roughly \(O(2^{N/2}\,N)\)) - Space complexity: \(O(2^{n_1} + 2^{n_2})\)

Implementation Notes

• Subset sum enumeration can be written concisely as sums.extend([sums[i] + a for i in range(m)]), extending based on “only the elements that currently exist.”

• Counting duplicates is important. The same sum appearing multiple times means different selections exist, so we need to add c1 * c2.

• \(S\) and \(A_i\) can be up to \(10^{12}\), but Python’s integers do not overflow, so they can be handled directly.

• Since inputs can be large, using sys.stdin.buffer.read() provides more stable reading.

  Source Code

import sys

def all_sums(arr):
    sums = [0]
    for a in arr:
        m = len(sums)
        sums.extend([sums[i] + a for i in range(m)])
    return sums

def main():
    data = sys.stdin.buffer.read().split()
    N = int(data[0])
    S = int(data[1])
    A = list(map(int, data[2:]))

    n1 = N // 2
    left = A[:n1]
    right = A[n1:]

    L = all_sums(left)
    R = all_sums(right)
    L.sort()
    R.sort()

    i, j = 0, len(R) - 1
    ans = 0

    while i < len(L) and j >= 0:
        s = L[i] + R[j]
        if s == S:
            v1 = L[i]
            c1 = 0
            while i < len(L) and L[i] == v1:
                c1 += 1
                i += 1

            v2 = R[j]
            c2 = 0
            while j >= 0 and R[j] == v2:
                c2 += 1
                j -= 1

            ans += c1 * c2
        elif s < S:
            v1 = L[i]
            while i < len(L) and L[i] == v1:
                i += 1
        else:
            v2 = R[j]
            while j >= 0 and R[j] == v2:
                j -= 1

    print(ans)

if __name__ == "__main__":
    main()

This editorial was generated by gpt-5.2-high.