Lab 3.2.2 Knapsack problem
You cannot submit for this problem because the homework's deadline is due.
Description
Use python3 to implement the correct solution of Knapsack problem (Subset sum problem).
The set only contains positive numbers, and the solution for the problem is unique. Therefore, you do not need to consider multiple solutions when you are trying to solve this problem.
Submission Format
Submit a tar or zip file including a script named knapsack.py.
IO
Input
The first line contains the sum S.
The second line contains the set of numbers, separated by single space.
Output
If there is a subset summing up to S, output the subset in sorted order.
If there is not, output nothing.
Sample IO
Sample 1
input
4
1 2 5
output
There is nothing in this output, even without any space or line breaks.
Sample 2
input
0
1 3 4 5
output
An empty set have a sum equals to 0.
[]
Sample 3
input
7
1 3 4 5
output
[3, 4]