0/1 Knapsack (Dynamic Programming)

canPartition.cpp

bool canPartition(vector<int>& nums) {
    const int sum = std::accumulate(nums.begin(), nums.end(), 0);
    if(sum % 2 != 0) return false;
    vector<bool> dp(sum+1, false);
    dp[0] = true;
    for( const int num : nums){
        for(int i = sum; i >= 0; i--){
            if(dp[i]) dp[i+num]=true;
        }
        if(dp[sum/2])
            return true;
    }
    return false;
}