416. Partition Equal Subset Sum

2D array

class Solution {
public:
    bool canPartition(vector<int>& nums)
    {
        int sum = accumulate(nums.begin(), nums.end(), 0);

        if (sum & 1) return false;

        int n = nums.size();
        int subset_sum = sum / 2;
        vector<vector<bool>> dp(n + 1, vector<bool>(subset_sum + 1));
        dp[0][0] = true;

        for (int i = 1; i <= n; i++)
        {
            int cur = nums[i - 1];
            for(int j = 0; j <= subset_sum; j++) {
                if(j < cur) dp[i][j] = dp[i - 1][j];
                else dp[i][j] = dp[i - 1][j] || (dp[i - 1][j - cur]);
            }
        }
        return dp[n][subset_sum];
    }
};

DP improved

class Solution {
public:
    bool canPartition(vector<int>& nums)
    {
        int sum = accumulate(nums.begin(), nums.end(), 0);

        if (sum & 1) return false;

        int target = sum >> 1;
        vector<bool> dp(target + 1);
        dp[0] = true;

        for (int num : nums)
        {
            for (int i = target; i >= num; --i)
            {
                dp[i] = dp[i] || dp[i - num];
                if (dp[target])
                {
                    return dp[target];
                }
            }
        }
        return dp[target];
    }
};