nord vpnnord vpn
Ad

sumitup

 avatar
duyvan
plain_text
16 days ago
1.3 kB
1
Indexable
Never
#include <iostream>
using namespace std;
int t, N, a[15], b[15];
int res, cnt;
bool ok = false;

void dfs(int dep, int sum, int pos){
	if(sum==t){
		ok=true;
		cnt++;
		return;
	}
	if(sum>t) return;
	if(pos>=N) return;
	b[dep] = a[pos];
	dfs(dep+1,sum+a[pos],pos+1);
	while(pos+1<N && a[pos] == a[pos+1])	pos++;
	dfs(dep,sum,pos+1);
}
int main(){
	int T; cin >> T;
	for(int tc=1; tc<=T; tc++){
		cin >> t >> N;
		for(int i=0; i<N; i++){
			cin >> a[i];
		}
		cnt = 0;
		ok = false;
		dfs(0,0,0);
		if(ok==false)	cout << "#" << tc << " -1" << endl;
		else cout << '#' << tc <<" " << cnt << endl;
		
	}
	return 0;
}

/*
#include<iostream>
using namespace std;

int t, n, a[20], b[20];
int ans;
void dfs(int s, int k, int g){
	int i;
	if(s > t) return;
	if(s == t){
		ans ++;
		return;
	}
	int last = -1;
	for(int i = k; i < n; i++){
		if(s+a[i] > t) continue;
		if(a[i] != last){
			last = b[g] = a[i];
			dfs(s+a[i], i+1, g+1);
		}
	}
}

int main(){
//	freopen("input.txt", "r",stdin);
	int T;
	cin >> T;
	for(int tc = 1; tc <= T; tc++){
		cin >> t >> n;
		ans = 0;
		for(int i = 0; i < n; i++){
			cin >> a[i];
		}
		dfs(0, 0, 0);
		cout << "#" << tc << " ";
		if(ans == 0) cout << -1 << endl;
		else{cout << ans << endl;}
	}
	return 0;
}

*/
Leave a Comment


nord vpnnord vpn
Ad