416. Partition Equal Subset Sum

Given a non-empty array nums containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

class Solution {
    unordered_set<int> v[200];
    bool dfs(int s, int i, vector<int>& nums, int& target) {
        if(i == nums.size()) return (s<<1) == target;
        if(v[i].count(s) or s<<1 >= target) return false;
        v[i].insert(s);
        if(dfs(s + nums[i], i + 1, nums, target)) return true;
        return dfs(s,i + 1, nums, target);
    }
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        return !(sum & 1) and dfs(0,0,nums,sum);
    }
};

• 0/1 Knapsack solution

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum & 1) return false;
        sum >>= 1;
        int n = nums.size();
        vector<vector<bool>> dp(n+1, vector<bool>(sum+1, false));
        for(int i = 0; i <= n; i++) dp[i][0] = true;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= sum; j++) {
                if(nums[i-1] <= j) dp[i][j] = (dp[i-1][j] || dp[i-1][j-nums[i-1]]);
                else dp[i][j] = dp[i-1][j];
            }
        }
        return dp[n][sum];
    }
};

• make all combination result with bitset

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if(sum & 1) return false;
        bitset<10001> bi(1);
        for(auto& n : nums) bi |= bi<<n;
        return bi[sum>>1];
    }
};