[问答题]
//这个是求解的,复杂度应该是解空间的大小
void out(int ary[], int n)
{
for (int i = 0; i < n; i++) {
printf("%d ", ary[i]);
}
printf("\n");
}
bool kubi(int sum, int ary[], int max, int level = 0)
{
bool flag = false;
if (max >= sum) {
ary[level] = sum;
out(ary, level + 1);
flag = true;
max = sum - 1;
}
for (int i = max; i > 0; i--) {
ary[level] = i;
if (kubi(sum - i, ary, i - 1, level + 1))
flag = true;
else
break;
}
return flag;
}
void out(int ary[], int n)
{
for (int i = 0; i < n; i++) {
printf("%d ", ary[i]);
}
printf("\n");
}
bool kubi(int sum, int ary[], int max, int level = 0)
{
bool flag = false;
if (max >= sum) {
ary[level] = sum;
out(ary, level + 1);
flag = true;
max = sum - 1;
}
for (int i = max; i > 0; i--) {
ary[level] = i;
if (kubi(sum - i, ary, i - 1, level + 1))
flag = true;
else
break;
}
return flag;
}
编辑于 2016-09-04 20:52:08
回复(0)
思路：将数组拆分成两个子数组，如果两个子数组的和相等，那么则输出两个子数组，并且计数加一；
int max(int num[],int n){
int Max=num[0];
for(int i=1;i<n;i++){
if(num[i]>Max){
Max=num[i];
}
}
return Max;
}
int min(int num[],int n){
int Min=num[0];
for(int i=0;i<n;i++){
if(num[i]<Min){
Min=num[0];
}
}
return Min;
}
void split(int num[],int n){
int sum=0;
int num1[n-1],num2[n-1];
for(int i=0;i<n;i++){
sum+=num[i];
}
if(sum%2==0){
if(max(num,n)>sum/2)
return;
else{
//如果数组中最大的数不超过总和的一半，那么应该可以分成两组
if(max(num,n)<sum/2){
if(max(num,n)+min(num,n)>sum/2)
return;
}
else{//最大数为总和的一半
num1[0]=max(num,n);
}
}
}
}
发表于 2015-06-23 11:16:00
回复(0)
问题信息
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
#include <iostream> using namespace std; #define MAXN 100 void dfs(int pi,int curSum,bool res[],int n,int half,int &num,int left[]) { for(int i=pi+1;i<=n;i++) { res[i]=true; if(curSum+left[i]=1;i--) left[i]=i+left[i+1]; dfs(0,0,res,n,half,cnt,left); return cnt; } int main() { int n=20; int num=cal_num(n); printf("num=%d\n",num); return 0; }