nums = [1, 5, 11, 5], target = 11

初始：dp = [T, F, F, F, F, F, F, F, F, F, F, F]
            0  1  2  3  4  5  6  7  8  9 10 11

处理num=1（倒序，j从11到1）：
  j=1: dp[1] |= dp[0] → T
dp = [T, T, F, F, F, F, F, F, F, F, F, F]

处理num=5（倒序，j从11到5）：
  j=11: dp[11] |= dp[6] → F（dp[6]=F）
  j=6: dp[6] |= dp[1] → T
  j=5: dp[5] |= dp[0] → T
dp = [T, T, F, F, F, T, T, F, F, F, F, F]

处理num=11（倒序，j从11到11）：
  j=11: dp[11] |= dp[0] → T ✓

三、解法一：标准01背包布尔DP

public class PartitionEqualSubsetSum {
    
    /**
     * 416. 分割等和子集 - 01背包布尔DP
     * 时间复杂度：O(n * target)，n为数组长度，target为总和的一半
     * 空间复杂度：O(target)
     */
    public boolean canPartition(int[] nums) {
        int sum = 0;
        for (int num : nums) sum += num;
        
        // 总和为奇数，无法平分
        if (sum % 2 != 0) return false;
        
        int target = sum / 2;
        
        // 特殊情况：如果单个元素超过target，肯定不行
        for (int num : nums) {
            if (num > target) return false;
        }
        
        // dp[j] = 是否存在子集和恰好为j
        boolean[] dp = new boolean[target + 1];
        dp[0] = true;  // 空子集和为0，可达
        
        // 01背包：外层物品，内层倒序容量
        for (int num : nums) {
            // 倒序遍历，防止重复使用同一个num
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
            // 提前退出优化
            if (dp[target]) return true;
        }
        
        return dp[target];
    }
}

Mermaid状态转移图：

四、解法二：位运算优化

这是一个很炫的技巧，把整个 boolean[] dp 压缩成一个整数的二进制位。

核心思想：用一个 long（或 BigInteger）的每一个二进制位表示 dp[i]：

第 i 位为1：表示 dp[i] = true
第 i 位为0：表示 dp[i] = false

初始状态：只有第0位为1，即 bits = 1（二进制：...0001）

处理每个 num 时，执行：

bits = bits | (bits << num)

原理分析：

bits << num 把所有为1的位左移 num 位，等于"在所有可达的 j 上加 num，得到新的可达值"。

bits | (bits << num) 把原来可达的和新增可达的合并，正好对应 dp[j] = dp[j] || dp[j - num]。

这一行代码就完成了整个内层循环！

/**
 * 416. 分割等和子集 - 位运算优化
 * 时间复杂度：O(n * target / 64)，因为64位并行计算
 * 空间复杂度：O(target / 64)
 */
public boolean canPartitionBit(int[] nums) {
    int sum = 0;
    for (int num : nums) sum += num;
    if (sum % 2 != 0) return false;
    
    int target = sum / 2;
    
    // 使用BigInteger，支持任意位数
    // 初始bit[0]=1，代表dp[0]=true
    java.math.BigInteger bits = java.math.BigInteger.ONE;
    
    for (int num : nums) {
        // bits | (bits << num) 等价于完整的内层循环
        bits = bits.or(bits.shiftLeft(num));
    }
    
    // 检查第target位是否为1
    return bits.testBit(target);
}

/**
 * 如果target <= 63，可以直接用long做位运算（更快）
 */
public boolean canPartitionLong(int[] nums) {
    int sum = 0;
    for (int num : nums) sum += num;
    if (sum % 2 != 0) return false;
    
    int target = sum / 2;
    if (target > 63) {
        // target超出long范围，退回布尔DP
        return canPartition(nums);
    }
    
    long bits = 1L;
    for (int num : nums) {
        bits |= (bits << num);
    }
    
    // 检查第target位
    return (bits >> target & 1) == 1;
}

位运算原理的图解：

初始 bits = 0001 (表示dp[0]=true)

处理 num=1：bits |= (bits << 1)
  bits << 1 = 0010
  bits | 0010 = 0011  （dp[0]=T, dp[1]=T）

处理 num=5：bits |= (bits << 5)
  bits << 5 = 0110_0000
  bits | 0110_0000 = 0110_0011 （dp[0,1,5,6]=T）

处理 num=11：bits |= (bits << 11)
  bits << 11 = 0001_1000_0001_1000_0000_0000
  合并后 bit[11]=1 ✓

五、解法三：记忆化DFS（自顶向下）

/**
 * 416. 分割等和子集 - 记忆化DFS
 * 时间复杂度：O(n * target)
 * 空间复杂度：O(n * target)（记忆化数组）
 */
public boolean canPartitionDFS(int[] nums) {
    int sum = 0;
    for (int num : nums) sum += num;
    if (sum % 2 != 0) return false;
    int target = sum / 2;
    
    // memo[i][j] = 考虑nums[i..]，能否凑成余量j
    // 0:未计算，1:可行，-1:不可行
    int[][] memo = new int[nums.length][target + 1];
    return dfs(nums, 0, target, memo);
}

private boolean dfs(int[] nums, int idx, int remain, int[][] memo) {
    if (remain == 0) return true;
    if (idx >= nums.length || remain < 0) return false;
    if (memo[idx][remain] != 0) return memo[idx][remain] == 1;
    
    boolean result = dfs(nums, idx + 1, remain - nums[idx], memo)  // 选nums[idx]
                  || dfs(nums, idx + 1, remain, memo);               // 不选nums[idx]
    
    memo[idx][remain] = result ? 1 : -1;
    return result;
}

六、举一反三

同类01背包可行性题目：

LeetCode 494. 目标和：布尔变计数，用+代替||
LeetCode 1049. 最后一块石头的重量II：本质也是01背包，求尽量接近sum/2的子集和
LeetCode 698. 划分为k个相等的子集：多个背包，用回溯+剪枝

布尔背包通用模板：

boolean[] dp = new boolean[target + 1];
dp[0] = true;
for (int item : items) {
    for (int j = target; j >= item; j--) {  // 01背包倒序
        dp[j] = dp[j] || dp[j - item];
    }
}
return dp[target];

七、踩坑实录

坑一：忘记处理sum为奇数的情况

sum为奇数时，无法平分，直接返回false。这个边界漏了，会导致target = sum/2是一个截断的整数，结果完全错误。

坑二：01背包内层不倒序

如果内层正序遍历，就变成完全背包，同一个num可以被无限次使用。nums=[1,5,11,5]，target=11，正序时可以用11个1凑成11，但实际上只有一个1，应该返回true只是因为巧合，换别的case就出错了。

坑三：位运算中bits左移超出范围

用long做位运算时，long只有64位，如果target>63就溢出了。题目中nums[i]≤100，nums.length≤200，最大sum=20000，target≤10000，远超64位。所以long版本只适用于target≤63的情况，一般情况要用BigInteger或者直接用布尔数组DP。

坑四：提前退出的时机

在01背包的内层循环里如果dp[target]已经是true，可以提前退出，但要在外层每次更新后检查，而不是在内层检查（内层是倒序遍历，只要找到一个true就行）。

八、总结

分割等和子集是01背包可行性问题的经典代表。

三种解法对比：

解法	时间复杂度	空间复杂度	特点
布尔DP	O(n×target)	O(target)	标准，易理解
位运算（BigInteger）	O(n×target/w)	O(target/w)	常数小，代码简洁
记忆化DFS	O(n×target)	O(n×target)	直观，但空间更大

核心记忆点：01背包的布尔DP，内层倒序遍历，转移用 ||。位运算优化把整个内层循环压缩成一次 bits |= bits << num，非常优雅。