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; } */
Leave a Comment