3,若对于整数N,在集合{1,2……,N}中找出m个数,使其和等于剩下的N-m个数的和。返回所有可能的组合数。N<10000。
#include "stdafx.h"
#include <iostream>
#include "sc.h"
#include <vector>
#include <stack>
using namespace std;
//打印vector
void print(vector<int> &ivec)
{
for(vector<int>::iterator iter=ivec.begin(); iter !=ivec.end(); iter++)
cout<<*iter<<" ";
cout<<endl;
}
//在数组a内查找等于tar的数列,len为数组长度,index为开始下标
bool sear(int a[], int tar, int len, int index)
{
static vector<int> ivec;
bool result=false;
if(tar==0)
{
print(ivec); //将符合条件的数列打印出来
return true;
}
if(tar<0)
{
return false;
}
for(int i=index; i<len; i++)
{
ivec.push_back(a[i]);
result=sear(a, tar-a[i], len, i+1);
ivec.pop_back();
}
return result;
}
void xunlei(int a[], int n)
{
int sum=0;
for(int i=0; i<n; i++)
sum+=a[i];
if(sum%2!=0)
{
cout<<"It doesn't exist the number queue!/n";
}
else
{
sear(a,sum/2,n,0);
}
}
void main()
{
int a[]={1,2,3,4,5,6,7,8};
xunlei(a, sizeof(a)/sizeof(int));
}