题目

解法：位集DP

思路

核心思想是将问题转化为子集和问题，使用 bitset 优化的动态规划。第一段：将数组分割成两个等和子集的问题等价于判断是否存在一个子集，其元素和等于数组总和的一半。使用 bitset 进行状态压缩的动态规划，通过位运算高效地计算所有可达的和。第二段：正确性基于 0/1 背包问题的状态转移。dp[i] 为 true 表示可以从前 k 个元素中选出若干个数使其和为 i。对于每个数字 num，dp << num 表示所有已可达的和加上 num 后变为新的可达和，dp |= (dp << num) 将新可达的和合并到状态中。由于正整数不会导致和回退，这种更新方式不会遗漏任何可能解。第三段：

• Step 1: 计算数组总和，若为奇数直接返回 false
• Step 2: 初始化 bitset dp，设置 dp[0] = 1
• Step 3: 遍历每个数字 num，执行 dp |= (dp << num)
• Step 4: 返回 dp[target] 的结果

复杂度

• 时间复杂度: $O(n \times \text{target})$，其中 n 是数组长度，target 是总和的一半。主要耗时在遍历每个数字并更新 bitset
• 空间复杂度: $O(\text{target})$，使用大小为 10001 的 bitset 存储状态

代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(int x: nums) sum += x;

        if(sum % 2) return false;

        int target = sum/2;

        bitset<10001> dp;
        dp[0] = 1;

        for(int num: nums){
            dp |= (dp << num);
        }

        return dp[target];
    }
};