|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 |
#include <iostream> #include <cstring> #include <cstdio> #include <algorithm> #define ll long long using namespace std; int sz[25]; ll sum; bool f; int total_piece; int stick_size; bool visit[25]; int M; bool cmp(int a,int b) { return a>b; } bool backtrack(int present_size,int index,int piece_cnt) { if(stick_size*piece_cnt==sum) return 1; for(int i=index;i<M;i++) { if(visit[i]) continue; if(i>0 && !visit[i-1] && sz[i]==sz[i-1]) continue; if(present_size+sz[i]==stick_size) { visit[i]=1; if(backtrack(0,0,piece_cnt+1)) return 1; visit[i]=0; return 0; } else if(present_size+sz[i]<stick_size) { visit[i]=1; if(backtrack(present_size+sz[i],i+1,piece_cnt)) return 1; visit[i]=0; if(present_size==0) return 0; } } return 0; } int main() { int t; int mx_sz; cin>>t; while(t--) { cin>>M; mx_sz = 0; sum = 0; for(int i=0;i<M;i++) { cin>>sz[i]; sum+=sz[i]; if(sz[i]>mx_sz) mx_sz = sz[i]; } if(sum%4) { cout<<"no\n"; continue; } if(mx_sz>sum/4) { cout<<"no\n"; continue; } sort(sz,sz+M,cmp); memset(visit,0,sizeof(visit)); stick_size = sum/4; if(backtrack(0,0,0)) cout<<"yes\n"; else cout<<"no\n"; } return 0; } |