leetcode--Partition Equal Subset Sum分区等子集和问题

第一种解法
dp[j] = dp[j] || dp[j - nums[i]] (nums[i] <= j <= target)

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

第二种解法
dp[i][j]=dp[i-1][j]|dp[i-1][j-nums[i]]

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

    
};

第三种解法
递归

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = accumulate(nums.begin(), nums.end(), 0);
        if (sum % 2 != 0)
            return false;
        return hasSubsetSum(nums, 0, sum / 2);
    }
private:
    bool hasSubsetSum(const vector<int> &nums, size_t start, int target) {
        if (target < 0)
            return false;
        if (target == 0)
            return true;
        for (size_t i = start; i < nums.size(); ++i)
            if (hasSubsetSum(nums, i + 1, target - nums[i]))
                return true;
        return false;
    }
};