首页 > 试题广场 >

将一个集合拆分成两个不相交的子集，两个子集元素之和相等，如{

[问答题]
将一个集合拆分成两个不相交的子集，两个子集元素之和相等，如{1, 2, 3, 4, 5, 6, 7}，拆分成： {2, 5, 7}, {1, 3, 4, 6} 给出一个集合，求所有符合上面要求的拆分，效率最高分越高，函数原型为int cal_num(int n);
添加回答
推荐
阿守头像 阿守 
#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;
}

编辑于 2015-05-29 22:06:20 回复(2)
do-you头像 do-you
//这个是求解的,复杂度应该是解空间的大小
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)
nimei1头像 nimei1
答案有问题啊
发表于 2015-09-06 23:25:34 回复(0)
ABCD头像 ABCD
思路：将数组拆分成两个子数组，如果两个子数组的和相等，那么则输出两个子数组，并且计数加一；
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)
提交观点

问题信息

C++工程师 数组 C++ 迅雷 2014
来自：迅雷2014C++笔试卷A
上传者：马特殊
难度：
4条回答 13866浏览

热门推荐

相关试题

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号