416 分割等和子集

· 2025-4-7   · 次阅读   · 字数统计: 206字   · 阅读时长≈ 1分钟

  · 算法题解   · LeetCode

题目链接

416. 分割等和子集

分析

首先求数组和，对于数组和为奇数的情况无法分割。

数组和为偶数的情况下，为01背包问题

设 $dp[i][j]$ 为前 $i$ 个数是否可以凑出和为 $j$ 的子集

状态转移方程为 $dp[i][j] = dp[i - 1][j] \ dp[i][j - nums[i]]$

答案为 $dp[x]$ ，$x$ 为数组之和的一半

代码实现

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum & 1)
            return false;
  
        int h = sum >> 1;
        vector<int> dp(h + 1, false);
        dp[0] = true;

        for(int i = 0; i < nums.size(); ++i) {
            for(int j = h; j >= nums[i]; --j) {
                dp[j] |= dp[j - nums[i]];
            }
        }

        return dp[h];
    }
};

复杂度分析

  • 时间复杂度：$O(n^2)$
  • 空间复杂度：$O(n)$