01背包

1.计算总和，判断集合中选一些数是否能凑得总和的一半。（需要特判总和为奇数无解的情况）

2.做一遍01背包

状态表示：f[i][j]表示从前i个物品中选，是否能凑出体积为j的 方案

状态转移：f[i][j] = f[i - 1][j] | f[i - 1][j - v]，分别对应选或者不选第i个物品

初始化：f[0 - n][0] = true 从所有数中选体积为0是一定可以凑出的，其余为false即可。

$ 时间复杂度O(NM)，空间复杂度O(M) $

参考文献

lc究极班

AC代码

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n = nums.size();
        int sum = 0;
        for (auto x : nums) sum += x;
        if (sum & 1) return false;//和为奇数，无解
        int m = sum / 2;
        //01背包
        vector<bool> f (m + 1, false);
        f[0] = true;
        for (auto x : nums){
            for (int j = m ; j >= x ; j --){
                f[j] = f[j] | f[j - x];
            }
        }
        return f[m];
    }
};