Overview

Given \(N\) types of sweets, select some of them such that the total price is exactly \(S\) yen. Find the number of ways to do this.

Analysis

This problem is an application of the classic subset sum problem: “How many ways are there to select a subset whose sum equals \(S\)?” However, due to the tight constraints, a simple brute-force search will not be fast enough.

For example, since each sweet has two choices — “buy” or “don’t buy” — there are \(2^N\) total possible selections. Since \(N\) can be up to \(40\), we get \(2^{40} \approx 10^{12}\), which cannot be computed within a realistic time limit.

This is where the technique called meet in the middle comes in. We split the array into two halves — the first half and the second half — and enumerate all subset sums for each half. This reduces the time complexity from \(O(2^N)\) to \(O(2^{N/2})\).

Specifically: - Compute all subset sums for the first half and record their frequencies in a hash table (dictionary). - Do the same for the second half. - Finally, count the number of combinations where “first half sum + second half sum = \(S\)”.

For example, if there are \(a\) subsets in the first half with sum \(x\), and \(b\) subsets in the second half with sum \(S - x\), then the product \(a \times b\) gives the number of valid selections for that particular pair.

In this way, we can find the answer while significantly reducing the computational cost.

Algorithm

1. Split the array \(A\) into the first half left and the second half right.
2. For all subsets of left, compute the sum of their elements and record it in a dictionary called left_sums (key: sum, value: number of subsets with that sum).
3. Similarly, create right_sums for right.
4. For each key \(ls\) in left_sums, if \(S - ls\) exists in right_sums, add their product to the answer.
5. Output the answer.

Complexity

• Time complexity: \(O(N \cdot 2^{N/2})\)
• Space complexity: \(O(2^{N/2})\)

Implementation Notes

• By using defaultdict(int), keys that don’t exist are automatically treated as having a default value of 0 without causing errors.

• Bit operations (bitmask) are used to enumerate subsets.

• sys.stdin.read is used for fast input reading.

  Source Code

from collections import defaultdict

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

    # 半分全列挙
    mid = N // 2
    left = A[:mid]
    right = A[mid:]

    # 左半分のすべての部分集合の和を計算
    left_sums = defaultdict(int)
    for mask in range(1 << len(left)):
        s = 0
        for i in range(len(left)):
            if mask & (1 << i):
                s += left[i]
        left_sums[s] += 1

    # 右半分のすべての部分集合の和を計算
    right_sums = defaultdict(int)
    for mask in range(1 << len(right)):
        s = 0
        for i in range(len(right)):
            if mask & (1 << i):
                s += right[i]
        right_sums[s] += 1

    # 結果を計算
    count = 0
    for ls, lc in left_sums.items():
        need = S - ls
        if need in right_sums:
            count += lc * right_sums[need]
    
    print(count)

if __name__ == "__main__":
    main()

This editorial was generated by qwen3-coder-480b.