# sumitup

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;
}

*/```