dp solution


  • 0
    Y
    class Solution {
    public:
        bool canPartition(vector<int>& nums) {
            int sum = 0;
            for (auto num: nums) {
                sum += num;
            }
            if (sum % 2) {
                return false;
            }
            vector<bool> dp(sum/2+1, false);
            dp[0] = true;
            for (auto num: nums) {
                for (int i = dp.size()-1; i >= num; i--) {
                    if (dp[i] == false && dp[i - num] == true) {
                        dp[i] = true;
                    }
                }
            }
            return dp[sum/2];
        }
    };
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.