力扣 416.分割等和子集 揹包問題

416.分割等和子集

給定一個只包含正整數的非空陣列。是否可以將這個陣列分割成兩個子集，使得兩個子集的元素和相等。

注意:

每個陣列中的元素不會超過 100
陣列的大小不會超過 200
範例 1:

輸入:

[1, 5, 11, 5]

輸出:

true

解釋: 陣列可以分割成 [1, 5, 5] 和 [11].

範例 2:

輸入:

[1, 2, 3, 5]

輸出:

false

解釋: 陣列不能分割成兩個元素和相等的子集.

思路：

先判斷總數是否是偶數，確定揹包容量，然後遍歷判斷揹包容量是否夠大，不夠大當前狀態則取決於上一個狀態，夠大則將揹包容量減少，即將該元素放入揹包中，再判斷狀態。

程式碼：

class Solution
{
public:
    bool canPartition(vector<int> &nums)
    {
        int tar = 0, n = nums.size();
        for (int i = 0; i < n; i++)
            tar += nums[i];
        if (tar % 2 != 0)   //判斷總和是否是偶數
            return false;
        tar /= 2;           //每個子集的和
        vector<bool> dp(tar + 1, false);
        dp[0] = true;       //database
        for (int i = 0; i < n; i++)
        {
            for (int j = tar; j >= 0; j--) //反向遍歷，保證每個元素只使用一次
            {
                if (j - nums[i] >= 0)
                {
                    dp[j] = dp[j] || dp[j - nums[i]];
                }
            }
        }
        return dp[tar];
    }
};