Untitled

Cho một tổng cụ thể t và một danh sách n số nguyên, tìm tất cả các tổng khác nhau 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 nhiều lần khi nó xuất hiện trong danh sách và một số duy nhấtber được tính là một tổng.) Công việc của bạn là giải quyết vấn đề này một cách tổng quát.

 

Đầu vào

Tệp đầu vào sẽ chứa một hoặc nhiều trường hợp thử nghiệm, mỗi trường hợp trên một dòng. Mỗi trường hợp thử nghiệm chứa t, tổng số, theo sau là n, số lượng các 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à các 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ể được lặp lại.

 

đầu ra

Đối với mỗi trường hợp kiểm tra, xuất ra tổng số cách, 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

in
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

#include <iostream>
using namespace std;
int array[1001];
int so[1001];
int visit[1001];
int compare[100][100];
int k,n,result;
int count1;

int check (int a){
	for(int i = 0; i < count1; i++){
		int dem = 0;
		for(int j = 0; j < a; j++){
			if(compare[i][j] == so[j]) dem++;
			else break;
		}
		if(dem == a) return 0;
	}
	return 1;
}

void backtrack(int a,int sum,int len){
	if(sum == k){
		if(check(len)){
			for(int i = 0; i < len ; i++){
				compare[count1][i] = so[i];
			}
			count1 ++;
			result ++;
		}
		return;
	}
	if(sum > k || a >= n) return;
	for(int i = 0; i < 2; i++){
		if(i == 0) backtrack( a + 1,sum,len);
		else{
			so[len] = array[a];
			backtrack(a + 1,sum + array[a],len+1);
			so[len] = 0;
		}
	}
}
int main(){
	///freopen("Text.txt","r",stdin);
	int T;cin >> T;
	for(int tc = 1; tc <= T; tc ++){
		cin >> k >> n;
		for(int i = 0; i < n; i++){
			cin >> array[i];
			so[i] = 0;
			for(int j = 0; j < n; j++){
				compare[i][j] = 0;
			}
		}

		result = 0;
		count1 = 0;
		backtrack(0,0,0);
		if(result != 0){
			cout << "#" << tc << " " << result << endl;
		}
		else cout << "#" << tc << " " << -1 << endl;
	}
	return 0;
}