天天看點

zju1204

#include<iostream>

using namespace std;

int a[30], n;

bool b[30], f;

bool BiSearch( int low, int dest )

{

       int high = n-1;

       int mid;

       while( low <= high )

       {

              mid = (low+high)/2;

        if( a[mid] == dest ) return true;

              else

              {

                     if( a[mid] < dest )

                            low = mid + 1;

            else high = mid - 1;

              }

       }

return false;

}

int cmp(const void*a,const void*b)

{

       return *(int *)a - *(int *)b;

}

void find(int start,int k,int sum)

{

       if(k==0)

       {

              //cout<<sum<<endl;

              if(BiSearch(start,sum))

              {

                     f=true;

                     for(int i=0;i<start-1;i++)

                         if(b[i])

                                cout<<a[i]<<'+';

                     cout<<a[start-1]<<'='<<sum<<endl;

              }

       }

       if(n-start<k)

              return;

       for(int low=start;low<n;low++)

       {

              b[low]=true;

              if(sum+a[low]<=a[n-1])

                     find(low+1,k-1,sum+a[low]);

              b[low]=false;

       }

}

int main()

{

int i, test;

memset(b,1,30);

scanf("%d",&test);

while( test -- )

{

    scanf("%d",&n);

    for( i = 0; i < n; i ++ )

    {

     scanf("%d",&a[i]);

    }

    qsort(a,n,sizeof(a[0]),cmp);

    f = false;

    for( i = 2; i <= n-1 ; i ++ )

    {

              find(0,i,0);

    }

    if( !f )

     cout<<"Can't find any equations."<<endl;

    cout<<endl;

}

return 0;

}

繼續閱讀