Untitled

mail@pastecode.io avatar
unknown
plain_text
a year ago
1.2 kB
1
Indexable
Never
#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;
}