#C4583. Exact Fuel Tank Selection
Exact Fuel Tank Selection
Exact Fuel Tank Selection
In this problem, you are given a required fuel amount F and a collection of fuel tanks with various capacities. Your task is to determine whether it is possible to select a subset of these tanks such that the sum of their capacities is exactly F. If such a subset exists, output "YES" on one line and on the next line output the selected tank capacities (separated by a space). Otherwise, print "NO".
The problem is equivalent to solving the subset sum problem. Mathematically, given a set of capacities (a_1, a_2, \dots, a_N) and a target fuel value (F), determine if there exists a subset (S) such that:
If multiple valid subsets exist, any one of them is acceptable.
inputFormat
The input starts with an integer T representing the number of missions (test cases). Each mission consists of two lines:
- The first line contains two integers F and N, where F is the required fuel and N is the number of tanks.
- The second line contains N space-separated integers representing the capacities of the fuel tanks.
outputFormat
For each mission, if a valid subset of tanks exists whose capacities sum to F, output "YES" on the first line followed by a line containing the selected tank capacities (space-separated). If no such subset exists, output "NO" on a single line.## sample
3
15 5
1 3 4 8 10
23 4
10 14 7 5
1 1
1
YES
3 4 8
NO
YES
1
</p>