SuperSubset | Topcoder Archive

Problem Statement

You're given a sequence A of N positive integers and a positive integer Y.

Let S be any subset of the set {0, 1, 2, 3, ..., N-1}. The weight of S, denoted w(S), is defined as the number of subsets {x₁, x₂, ..., x_k} of S such that A[x₁] + A[x₂] + ... + A[x_k] = Y.

For example, suppose A = {1, 10, 40, 70, 71, 100, 111, 200} and Y = 111.
For the set S1 = {0, 1, 2, 3, 4, 5} we have w(S1) = 3 because of the three subsets {0, 1, 5}, {0, 2, 3}, and {2, 4}:

A[0] + A[1] + A[5] = 1 + 10 + 100 = 111,
A[0] + A[2] + A[3] = 1 + 40 + 70 = 111, and
A[2] + A[4] = 40 + 71 = 111.

For the set S2 = {2, 5, 6, 7} we have w(S2) = 1 because the only subset of S2 with the required property is {6}, with A[6] = 111.

Find the sum of w(S) over all subsets of the sequence {0, 1, 2, 3, ..., N-1}. Return this sum modulo 10⁹+7.

Definition

Class:: SuperSubset
Method:: solve
Parameters:: int[], int
Returns:: int
Method signature:: int solve(int[] A, int Y)
(be sure your method is public)

Constraints

A will have between 1 and 3000 elements, both inclusive.
A[i] will have between 1 and 9999, both inclusive.
Y will be between 1 and 9999, inclusive.

Examples

```
{1, 2, 3}
```
```
3
```
```
Returns: 6
```
w( { } ) = 0 w( { 1 } ) = 0 w( { 2 } ) = 0 w( { 3 } ) = 1 w( { 1, 2 } ) = 1 w( { 1, 3 } ) = 1 w( { 2, 3 } ) = 1 w( { 1, 2, 3 } ) = 2
```
{1, 1, 1, 1, 1}
```
```
4
```
```
Returns: 10
```
Each of the five 4-element sets of indices has weight 1 and the only 5-element set of indices has weight 5.

This problem statement is the exclusive and proprietary property of TopCoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of TopCoder, Inc. is strictly prohibited. (c)2024, TopCoder, Inc. All rights reserved.