集合等和划分问题

经验分享区
1

题解：
问题描述
给定一个从1到n的连续整数集合，要求将其划分为两个子集，使得两个子集的元素和相等。计算所有不同的划分方案数。

解题思路
这道题目可以采用折半枚举的优化方法来解决，主要思想是将集合分成两部分，分别计算可能的部分和，然后组合统计结果。

关键步骤
总和检查：首先计算1到n的总和，如果总和为奇数则直接返回0（无法平分）

折半处理：将集合分成前半部分和后半部分

部分和计算：

用位运算枚举前半部分所有可能的子集和

用哈希表记录每个和出现的次数

匹配计算：枚举后半部分的子集和，查找能使总和达到目标值的互补值

int main(){
    scanf("%d",&n);
    计算总和
    
    如果总和是奇数，直接输出0
    if(total & 1){
        puts("0");
        return 0;
    }
    
    目标值
    前半部分大小
    
     枚举前半部分所有子集
    for(int i=0; i<(1<<half); ++i){
        计算当前子集的和
        for(int j=0; (i>>j)>0; ++j)
            if((i>>j)&1) cur += (j+1);
        记录该和出现的次数
    }
    
     枚举后半部分所有子集
    for(int i=0; i<(1<<(n-half)); ++i){
        计算当前子集的和
        for(int j=0; (i>>j)>0; ++j)
            if((i>>j)&1) cur += (j+half+1);
        
         如果当前和不超过目标值，查找互补值
        if(target >= cur)
            ans += b[target - cur];
    }
    
    每种划分被计算了两次，需要除以2
    printf("%lld\n",ans/2);
    return 0;
}

时间复杂度：O(2^(n/2))
空间复杂度：O(M)，其中M是可能的和的最大值

1 个赞