Description

Submission

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        if(nums.size() == 1) return false;
        int total = 0;
        for(auto num : nums) {
            total += num;
        }
        if(total % 2 == 1) return false;

        int target = total / 2;

        unordered_set<int> prev;    
        prev.insert(0);

        for(auto num: nums) {
            unordered_set<int> added;
            for(auto p: prev) {
                if(p + num > target) {
                    continue;
                }
                if(p+num == target) return true;
                added.insert(p+num);
            }
            for(auto a: added){
                prev.insert(a);
            }
        }
        return false;
    }
};