###### tags: `Leetcode` `medium` `dynamic programming` `python` `c++` `Top 100 Liked Questions`

# 416. Partition Equal Subset Sum

## [題目連結:] https://leetcode.com/problems/partition-equal-subset-sum/

## 題目:
Given a **non-empty** array nums containing **only positive integers**, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

**Example 1:**

Input: nums = [1,5,11,5]
Output: true
Explanation: The array can be partitioned as [1, 5, 5] and [11].

**Example 2:**

Input: nums = [1,2,3,5]
Output: false
Explanation: The array cannot be partitioned into equal sum subsets.

## 解題想法:
* 此題為判斷數組是否能拆成兩部分使得兩部分和相等
* 使用dp:
* 定義**dp[i][j]**: **從nums[0]~nums[i]中，取隨意個數，能否構成j**
* dp[i][j]= **dp[ i-1 ][j]** or **dp[ i-1 ][ j-nums[i] ]**
* 對於遍歷到nums[i]時候:
* case dp[i-1][j]: **先前nums[0]~nums[i-1]之數字總和可構成j**
* 則不用取nums[i]，依然可以總和為j
* case dp[i-1][j-nums[i]]: **先前nums[0]~nums[i-1]之數字總和可構成 j-nums[i]**
* 則表示取了nums[i]後，可以構成總和j

* 流程:
* **Step1**: 初始判斷
* 若數組長度不足2 or 總和為奇數，則為False
* **Step2**: 初始dp
* **dp[i][0]=True**: 構成0只要不取任何數即可
* **dp[0][nums[0]]=True**: 構成nums[0]，只要取nums[0]即可
* **Step3**: 填入dp

## Python:

class Solution(object):
    def canPartition(self, nums):
        """
        :type nums: List[int]
        :rtype: bool
        """
        '''
        dp[i][j]: 從nums[0]~nums[i]中 取隨意個數 能否構成j
        dp[i][j] = dp[i-1][j] or dp[i-1][j-nums[i]] 
        遍歷到i位置時:
        case dp[i-1][j]: 前面i-1之數字總和可構成j:  則不用取nums[i]，依然可以總和為j
        case dp[i-1][j-nums[i]] 前面i-1之數字總和可構成 j-nums[i]: 則表示取了nums[i]後，可以構成總和j
        初始: 
        dp[i][0]:True  構成0只要不取任何數即可
        dp[0][nums[0]]: True  構成nums[0]只要取nums[0]即可
        '''
        if len(nums)<2:
            return False
        total=sum(nums)
        if total%2!=0: #若一半為奇數 也不用搞了
            return False
        target=total//2
		#不能用target+1，因為有可能某個nums[i]大於target以上
        dp= [[False]*(total+1) for _ in range(len(nums))] 
        #初始:
        dp[0][nums[0]]=True
        for i in range(len(nums)):
            dp[i][0]=True
        #填dp
        for i in range(1,len(nums)):
            for j in range(1,target+1):
                if j-nums[i]>=0:
                    dp[i][j]=dp[i-1][j]|dp[i-1][j-nums[i]]
                else:
                    dp[i][j]=dp[i-1][j]
        return dp[-1][target]


nums = [1,5,11,5]
result=Solution()
ans=result.canPartition(nums)
print(ans)

## C++:
* vector總和使用 **accumulate**(first_index, last_index, initial value of sum);

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