蒜头君手上有一些小木棍,它们长短不一,蒜头君想用这些木棍拼出一个等边三角形,并且每根木棍都要用到。例如, 蒜头君手上有长度为1, 2, 3, 3的4根木棍,他可以让长度为1,2的木棍组成一条边,另外2跟分别组成2条边,拼成一个边长为3的等边三角形。蒜头君希望你提前告诉他能不能拼出来,免得白费功夫。
输入格式
首先输入一个整数n(1<n<10),表示木棍数量,接下来输入n根木棍的长度m(1 <p<10000)。
输出格式
如果蒜头君能拼出等边三角形,输出\"yes\",否则输出\"no\"。
蒜头君手上有一些小木棍,它们长短不一,蒜头君想用这些木棍拼出一个等边三角形,并且每根木棍都要用到。例如, 蒜头君手上有长度为1, 2, 3, 3的4根木棍,他可以让长度为1,2的木棍组成一条边,另外2跟分别组成2条边,拼成一个边长为3的等边三角形。蒜头君希望你提前告诉他能不能拼出来,免得白费功夫。 输入格式 首先输入一个整数n(1<n<10),表示木棍数量,接下来输入n根木棍的长度m(1 <p<10000)。 输出格式 如果蒜头君能拼出等边三角形,输出\"yes\",否则输出\"no\"。 #include <iostream> using namespace std; int n; int a[15]; int sum=0; bool b; bool c[15]; void dfs(int g,int s){ if(g==3){ //如果能造三个木棍证明可以 b=1; return; } if(s==sum/3){ //造完一个木棍后,长度清零,数目加一 dfs(g+1,0); return; } for(int i=0;i<n;i++){ if(!c[i]){ //标记是否用过, c[i]=1; dfs(g,s+a[i]); //长度加上刚刚用到的木棍 c[i]=0; } } } int main(){ cin>>n; for(int i=0;i<n;i++){ cin>>a[i]; sum+=a[i]; } if(sum%3!=0){ //能拼成三角形一定能被3整除 cout<<"no"; }else{ dfs(0,0); //搜索,第一个0代表0个木棍,第二个代表木棍长度 if(b){ cout<<"yes"; } else{ cout<<"no"; } } return 0; }