Leetcode 416. Partition Equal Subset Sum

Partition Equal Subset Sum

把nums內的數字分成兩堆，兩堆數字分別的和要相等

Python

動態規劃 : 把加起來的合存到set裡(不會包含重複的資料)，不斷的比較是否有合相等的情況，因為set不會包含重複的資料，所以可以一直比較。

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if sum(nums)%2: return 0

        st = set([0])
   
        for i in nums:
            for j in list(st):
                st.add(i + j)
                if i + j == sum(nums)//2:
                    return True
        return False

C++

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