题目描述:
输入int型数组,询问该数组能否分成两组,使得两组中各元素加起来的和相等,并且,所有5的倍数必须在其中一个组中,所有3的倍数在另一个组中(不包括5的倍数),能满足以上条件,输出true;不满足时输出false。
本题含有多组样例输入。
输入描述:
第一行是数据个数,第二行是输入的数据
输出描述:
返回true或者false
示例:
输入:
4
1 5 -5 1
3
3 5 8
输出:
true
false
说明:
第一个样例:
第一组:5 -5 1
第二组:1
第二个样例:由于3和5不能放在同一组,所以不存在一种分法。
解题思路:
这题可以用递归解决。首先输入n个数字,将5的倍数和3的倍数分别累加得到sum3和sum5,其他的数字放在容器v中;用add函数进行递归,单个数字从容器中提出来加到sum3或者sum5中,以此类推,直到所有数字都加进去了;之后,判断sum3和sum5是否一致,然后一级级返回标识符即可。
测试代码:
#include <iostream> #include <string> #include <vector> using namespace std; bool add(int sum5,int sum3,vector<int> v) { if(v.size()==0) { if(sum5==sum3) return true; else return false; } else{ int b=v.back(); v.pop_back(); return add(sum5+b,sum3,v)||add(sum5,sum3+b,v); } } int main() { int num; while(cin>>num) { int sum3=0; int sum5=0; vector<int> v; for(int i=0;i<num;++i) { int temp; cin>>temp; if(temp%5==0) sum5+=temp; else if(temp%3==0) sum3+=temp; else v.push_back(temp); } if(add(sum5,sum3,v)) cout<<"true"<<endl; else cout<<"false"<<endl; } return 0; }