Lab 3.2.2 Knapsack problem

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]

Lab3

Not Claimed
Status
Finished
Problems
3
Open Since
2019-10-01 00:00
DDL
2019-10-11 23:59
Extension
72.0 hour(s)