/*
编写一个函数，传入一个int型数组，返回该数组能否分成两组，
使得两组中各元素加起来的和相等，并且，所有5的倍数必须在其中一个组中，
所有3的倍数在另一个组中(不包括5的倍数)，能满足以上条件，返回true；
不满足时返回false。
*/
#include
#include
#include
using namespace std;
string myplus(string str)//用于将字符串加1，转换为下一个字符串
{
int length=str.length();
string str1(length,'0');
str1[length-1]='1';
int flag=0;
for(int i=length-1;i>=0;i--)
{
if(str[i]-'0'+str1[i]-'0'+flag>1)
{
str[i]='0';
flag=1;
}
else
{
char temp;
temp=str[i]-'0'+str1[i]-'0'+flag+'0';
str[i]=temp;
break;
}
}
return str;
}
bool canFind(vector& ivec,int sum)//判断一个数组中，是否存在一个或几个数的和为一个已知的特定值。用排列组合的方式，如果有n个数，则存在2^n种选择
{
sort(ivec.begin(),ivec.end());
vector::iterator itr=ivec.begin();
while(itr!=ivec.end())
if (*itr==sum) return true;
int count=ivec.size();
string str(ivec.size(),'0');
int count1=pow(2.0,count);
for(int i=1;i<=count1;i++)
{
int a1=0,b1=0;
for(int j=0;j
{
if(str[j]=='0')
a1=a1+ivec[j];
else if(str[j]=='1')
b1=b1+ivec[j];
}
if(abs(a1-b1)==sum)
{
return true;
}
str=myplus(str);
}
return false;
}
void FindNum(int *arr,int n, int sum)
{
int begin = 0;
int end = n-1;
while(begin < end)
{
if(sum == arr[begin]+arr[end])
{
cout<
return;
}
else if (sum > arr[begin]+arr[end])
begin++;
else
end--;
}
cout<
}
bool getArray(vector& ivec)
{
int len=ivec.size();
int i,sum=0,difference;
int sumofFive=0,sumofThree=0,sumofOthers=0;
int sum1,sum2;
vector others;
for(i=0;i
{
sum=sum+ivec[i];
if(ivec[i]%5==0) sumofFive+=ivec[i];
else if(ivec[i]%3==0) sumofThree+=ivec[i];
else
{
others.push_back(ivec[i]);
sumofOthers+=ivec[i];
}
}
if (sum%2!=0) return false;
else
{
difference=abs(sumofFive-sumofThree);
if(difference==sumofOthers)
return true;
else if(sumofOthers
return false;
else
{
sum1=(difference+sumofOthers)/2;
sum2=(sumofOthers-difference)/2;
if(canFind(others,sum2))
return true;
}
}
return false;
}
int main()
{
vector ivec;
int num;
cin>>num;
int data;
for(int i=0;i
{
cin>>data;
ivec.push_back(data);
}
if(getArray(ivec)) cout<
else cout<
return 0;
}
