题解 | #分割等和子集#

将任务看成是一个贪心算法，求得一组数据能使得其和为数组总值的一半即可。

#include<numeric>
class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param nums int整型vector 
     * @return bool布尔型
     */
    bool partition(vector<int>& nums) {
        // write code here
        int sum = accumulate(nums.begin(),nums.end(),0);
        if(sum % 2!=0)
            return false;
        int half = sum/2;
        
        vector<int> half_dig(half+1,0);
        half_dig[0] = 1;
        for(int j = 0; j < nums.size(); ++j){
            for(int i  = 0; i <= half; ++i){
                if(half_dig[i] == 1 && i+nums[j]<=half){
                    half_dig[i+nums[j]] = 1;
                    if(half_dig[half] == 1)
                        return true;
                }
            }
        }
        return false;
        
    }
};