Medium

题目描述

给你一个 只包含正整数 的 非空 数组 nums ，请你判断是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

示例 1：

输入：nums = [1,5,11,5]
输出：true
解释：数组可以分割成 [1, 5, 5] 和 [11] 。

示例 2：

输入：nums = [1,2,3,5]
输出：false
解释：数组不能分割成两个元素和相等的子集。

提示：

  • 1 <= nums.length <= 200
  • 1 <= nums[i] <= 100

解题思路

这是一个经典的背包问题变种，可以转化为：是否能从数组中选择一些数字，使它们的和等于总和的一半。

解题思路

首先进行预处理：

  1. 计算数组总和 sum
  2. 如果 sum 是奇数，直接返回 false（无法平分）
  3. 目标就是找到和为 sum/2 的子集

这个问题可以用动态规划解决，类似于0-1背包问题：

状态定义：dp[i] 表示是否能凑出和为 i 的子集

状态转移：对于每个数字 num，我们有选择和不选择两种情况：

  • 如果不选择 num，那么 dp[j] 保持不变
  • 如果选择 num，那么 dp[j] = dp[j-num]（前提是 j >= num）

因此转移方程为：dp[j] = dp[j] || dp[j-num]

空间优化：使用一维数组，从右向左更新，避免重复使用。

时间复杂度：O(n × target)，其中 n 是数组长度，target 是 sum/2 空间复杂度：O(target)

代码实现

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        
        // 如果总和是奇数，无法平分
        if (sum % 2 == 1) {
            return false;
        }
        
        int target = sum / 2;
        vector<bool> dp(target + 1, false);
        dp[0] = true; // 和为0总是可以达到（选择空集）
        
        for (int num : nums) {
            // 从右向左更新，避免重复使用
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        
        return dp[target];
    }
};

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        
        # 如果总和是奇数，无法平分
        if total % 2 == 1:
            return False
        
        target = total // 2
        dp = [False] * (target + 1)
        dp[0] = True  # 和为0总是可以达到（选择空集）
        
        for num in nums:
            # 从右向左更新，避免重复使用
            for j in range(target, num - 1, -1):
                dp[j] = dp[j] or dp[j - num]
        
        return dp[target]

public class Solution {
    public bool CanPartition(int[] nums) {
        int sum = 0;
        foreach (int num in nums) {
            sum += num;
        }
        
        // 如果总和是奇数，无法平分
        if (sum % 2 == 1) {
            return false;
        }
        
        int target = sum / 2;
        bool[] dp = new bool[target + 1];
        dp[0] = true; // 和为0总是可以达到（选择空集）
        
        foreach (int num in nums) {
            // 从右向左更新，避免重复使用
            for (int j = target; j >= num; j--) {
                dp[j] = dp[j] || dp[j - num];
            }
        }
        
        return dp[target];
    }
}

var canPartition = function(nums) {
    const sum = nums.reduce((a, b) => a + b, 0);
    if (sum % 2 !== 0) return false;
    
    const target = sum / 2;
    const dp = new Array(target + 1).fill(false);
    dp[0] = true;
    
    for (const num of nums) {
        for (let j = target; j >= num; j--) {
            dp[j] = dp[j] || dp[j - num];
        }
    }
    
    return dp[target];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n × target)n为数组长度，target为sum/2，每个元素需要更新target个状态
空间复杂度O(target)使用一维DP数组，长度为target+1

相关题目