tong ket lai

Tổng kết lại
Cho một tổng t xác định và một danh sách n số nguyên, hãy tìm tất cả các tổng riêng biệt bằng cách sử dụng các số từ danh sách có tổng bằng t. Ví dụ: nếu t = 4, n = 6 và danh sách là [4, 3, 2, 2, 1, 1] thì có bốn tổng khác nhau bằng 4: 4, 3+1, 2+2, và 2+1+1. (Một số có thể được sử dụng trong một tổng số lần nó xuất hiện trong danh sách và một sốber được tính là tổng.) Công việc của bạn là giải bài toán này nói chung.

 

Đầu vào

Tệp đầu vào sẽ chứa một hoặc nhiều trường hợp kiểm thử, mỗi trường hợp trên một dòng. Mỗi test chứa t, tổng, theo sau là n, số số nguyên trong danh sách, theo sau là n số nguyên x1, . . . ,xn. t sẽ là số nguyên dương nhỏ hơn 1000, n sẽ là số nguyên từ 1 đến 12 (đã bao gồm) và x1, . . . , xn sẽ là số nguyên dương nhỏ hơn 100. Tất cả các số sẽ cách nhau đúng một dấu cách. Các số trong mỗi danh sách có thể lặp lại.

 

đầu ra

Đối với mỗi trường hợp kiểm thử, xuất kết quả tổng, nếu không xuất ra -1.

 

Vật mẫu

Đầu vào

4

4 6

4 3 2 2 1 1

5 3

2 1 1

400 12

50 50 50 50 50 50 25 25 25 25 25 25

20 10

1 2 3 4 5 6 7 8 9 10

 

đầu ra

#1 4

#2 -1

#3 2

#4 31

 

Giải thích

#1

4

3+1

2+2

2+1+1

 

#3

50+50+50+50+50+50+25+25+25+25

50+50+50+50+50+25+25+25+25+25+25

 

#4

1+2+3+4+10

1+2+3+5+9

1+2+3+6+8

1+2+4+5+8

1+2+4+6+7

1+2+7+10

1+2+8+9

1+3+4+5+7

1+3+6+10

1+3+7+9

1+4+5+10

1+4+6+9

1+4+7+8

1+5+6+8

1+9+10

2+3+4+5+6

2+3+5+10

2+3+6+9

2+3+7+8

2+4+5+9

2+4+6+8

2+5+6+7

2+8+10

3+4+5+8

3+4+6+7

3+7+10

3+8+9

4+6+10

4+7+9

5+6+9

5+7+8






20
644 12
54 80 97 20 47 98 68 28 25 55 2 70 
498 12
60 70 15 4 32 44 93 37 21 25 38 59 
150 12
9 93 72 64 9 27 47 24 3 26 75 3 
499 11
57 33 43 12 42 35 8 61 49 73 86 
734 11
55 89 23 28 81 58 90 77 72 64 97 
302 12
61 100 72 28 7 26 18 60 70 61 62 39 
295 11
82 31 72 46 97 98 61 13 17 47 26 
201 10
62 63 2 46 39 95 71 58 69 99 
133 10
66 55 48 89 28 83 18 20 100 28 
272 11
55 24 43 94 38 78 68 3 25 94 22 
171 12
35 54 64 67 29 13 81 26 3 43 58 40 
207 12
49 73 4 62 18 40 95 69 35 33 96 49 
429 10
53 25 60 30 36 35 15 100 69 6 
226 10
68 51 75 64 13 75 85 96 60 92 
626 12
45 65 11 81 40 80 83 21 60 65 28 47 
407 12
79 96 81 82 42 45 89 90 88 72 38 13 
152 12
80 51 59 94 35 63 15 14 89 18 68 25 
350 12
1 73 75 58 86 64 49 52 88 60 45 49 
261 10
38 90 71 16 33 82 36 91 42 23 
692 10
100 87 93 69 29 53 62 76 50 73