Subset sum 5
Time: 2.0 s Memory: 16 MB
-
You are given $N$ integers. Your task is to determine whether there exists a subset of these integers, whose sum is exactly $T$. If such a subset exists, output any such subset. Please also note the unusual memory limit.
Input
The first line contains the integers $N$ and $T$ ($1 \leq N \leq 4000$, $0 \leq T \leq 2 \cdot 10^6$), the number of integers and the target sum.
The following line contains $N$ space-separated integers $a_1, a_2, \dots , a_N$ ($0 \leq a_i \leq T$), the integers described above.
Output
-
If there exists a subset of the input with sum equal to $T$, print YES.
On the next line, print a binary string of length $N$. The $i$:th character means that the $i$:th element in the input should be included your subset. If there are multiple valid subsets answers, you can print any of them. -
If there doesn’t exist a subset with sum $T$, print NO.
Sample Input 1 Sample Output 1 4 17 7 6 4 3
YES 1110
Sample Input 2 Sample Output 2 1 0 0
YES 0
Sample Input 3 Sample Output 3 4 10 1 2 3 4
YES 1111
Sample Input 4 Sample Output 4 2 5 3 3
NO
-
-
To solve the problems, you can either start a virtual contest or register for regular practice. A virtual contest simulates a participation in the original contest with a duration of 1 day, while regular practice lets you submit solutions without any constraints.
You must log in to register. - 1 Subset sum
- 2 Subset sum 2
- 3 Subset sum 3
- 4 Subset sum 4
- 5 Subset sum 5