416. Partition Equal Subset Sum 類似最小不可組成和

Given a non-empty array 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.

Note:

1. Each of the array element will not exceed 100.
2. The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].
      

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.
      

Seen this question in a real interview before? 

把一個數組分成兩組，看和是否相等。注意這不是連續數組。比如[3 4 6 5] 不能用區間和計算

思路：1個數選或不選。

首先求得總和，要求選其中的數的和是總和的一半。

建立矩陣dp[i][j]，表示j這個和能否由前i個數組成。

邊界條件： 

(1) dp[0][0]=true

（2）dp[i][0]=true,對于所有的i隻要一個數都不選，就可以了

（3）dp[0][j]=false 0個數不能組成1一上的數，隻能組成0

傳遞條件：

dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i]]  說明，如果前i-1個數能組成j，那麼前i個數一定能組成j，隻要不加nums[i]；如果前i-1個數能組成j-nums[i]，那麼前i個數能組成j，隻要将nums[i]加上即可。這兩種情況由一種滿足，目前值就是true。

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n=nums.size();
        if(n<=1) return false;
        int sum=accumulate(nums.begin(),nums.end(),0);
        if(sum&1) return false;
        sum/=2;
        vector<vector<bool>> dp(n+1,vector<bool>(sum+1,false));//這裡的i,從1位置表示幾個數，sum也是從1開始計算,因為0個數也要考慮，sum是求和的值，也包括0這個意義
        dp[0][0]=true;
        for(int i=1;i<=n;i++)
            dp[i][0]=true;
        //初始化dp[0][j]已經是false
        for(int i=1;i<=n;i++)
            for(int j=1;j<=sum;j++)
            {
                dp[i][j]=dp[i-1][j];//
                if(j>=nums[i-1])//有等号，和可以是0
                {
                    dp[i][j]=dp[i-1][j]||dp[i-1][j-nums[i-1]];//注意nums[i-1]是從0開始記得
                }
            }
        return dp[n][sum];
        
    }
};
           

空間優化：

發現橫坐标至于前面一行有關，而且j的周遊也是從小到大的。是以j應該從大到小更新，否則會覆寫舊知

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int n=nums.size();
        if(n<=1) return false;
        int sum=accumulate(nums.begin(),nums.end(),0);
        if(sum&1) return false;
        sum/=2;
        vector<bool> dp(sum+1,false);//這裡的i,從1位置表示幾個數，sum也是從1開始計算,因為0個數也要考慮，sum是求和的值，也包括0這個意義
        dp[0]=true;
        //初始化dp[0][j]已經是false
        for(int i=1;i<=n;i++)
            for(int j=sum;j>=1;j--)
            {
                if(j>=nums[i-1])//有等号，和可以是0
                {
                    dp[j]=dp[j]||dp[j-nums[i-1]];//注意nums[i-1]是從0開始記得
                }
            }
        return dp[sum];
        
    }
};