問題描述：

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:

• Each of the array element will not exceed 100.
• 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.

解題思路：

劃分成相等的子集和，容易得到以下性質(zhì)：

• 如果只有一個數(shù)，則肯定不能劃分；
• 如果所有數(shù)和為奇數(shù)，則肯定不能劃分；
• 劃分的目標(biāo)是所有數(shù)總和除以2。

方法1：使用貪心算法求解（錯誤思想，但是竟然 AC 了）：

• 先對所有數(shù)進行從大到小排序；
• 使用雙指針 i，j；i 指向當(dāng)前數(shù)字，j 向后移動；
• 雙循環(huán)，外層循環(huán) i 每次指向一個數(shù)字，內(nèi)層循環(huán) j 在移動的過程中：
  1、如果當(dāng)前累加和 < 目標(biāo)，則更新累加和；
  2、如果累積和 == 目標(biāo)，則返回 True；
  3、如果累加和 > 目標(biāo)，則什么都不做。
• 最后，如果不能劃分，返回 False。

例如：nums = [10,8,7,6,5,4]，第一次循環(huán)，i 指向 10，j 在遍歷的過程中，10 和 8 可以裝進去，但是后面的數(shù)字不行；第二次循環(huán)，i 指向 8，j 在遍歷的過程中，8、7 和 5 可以裝進去，并且正好等于 20，則返回 True。

Python3 實現(xiàn)如下：

class Solution:
    def canPartition(self, nums):
        lens = len(nums)
        if lens == 1:
            return False
        tot = sum(nums)
        if tot % 2 == 1:
            return False
        target = tot // 2
        nums.sort(reverse=True)  # 從大到小排序
        for i in range(lens):
            tem = 0
            for j in range(i, lens):
                if tem + nums[j] == target:
                    return True
                elif tem + nums[j] < target:
                    tem += nums[j]
        return False

print(Solution().canPartition([6,5,4,8,10,7]))  # True

雖然可以 AC，但是之后有人告訴我實際上這種貪心的思想是錯誤的，比如考慮：[23,13,11,7,6,5,5]，應(yīng)該返回 True（[23,7,5] 和 [13,11,6,5]），但是按照上述代碼的思想，會返回 False。竟然發(fā)現(xiàn)了 Leetcode 的一個 bug，哈哈哈~

方法2：使用動態(tài)規(guī)劃求解（正確思想）：

實際上，這道題是01-背包問題的應(yīng)用：01-背包、完全背包、多重背包及其相關(guān)應(yīng)用。

我們可以將問題轉(zhuǎn)化為以下的形式：是否有一個子數(shù)組的元素之和，恰好等于原數(shù)組元素之和的一半呢？而對于原數(shù)組中的每一個元素，都有兩種狀態(tài)：在子數(shù)組里面或者不在子數(shù)組里面（先假設(shè)存在這個子數(shù)組）。這樣一看，我們就能發(fā)現(xiàn)這個問題與0-1背包問題非常相似，因此我們可以采用0-1背包問題的解法去解決這道問題。

在這道題目中，原數(shù)組里面的每個元素都可以看作是一種物品，而這件物品的重量和價值都為元素值；原數(shù)組的和的一半可看作背包的最大承重量，而當(dāng)背包能放下物品的最大價值為原數(shù)組和的一半時，就返回真，否則返回假。

因此，我們就能很容易的得到以下算法：

• 在這個問題中，背包容量為數(shù)組和的一半，因此需要 dp[len(nums)+1][sum(nums)//2+1] 大小的數(shù)組，其中 dp[i][j] 表示前 i 個數(shù)放入容量為 j 的背包中的目標(biāo)值；
• 如果 j 小于當(dāng)前第 i 個數(shù)的容量，即 j < nums[i-1]，則 dp[i][j] = dp[i-1][j]；
• 否則，dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i-1]] + nums[i-1])；
• 在每填完表的一行時，就應(yīng)該判斷一下是否達到了目標(biāo)值，即 dp[i][j] 是否為 True，而不是等更新完表的所有行再判斷；
• 如果更新完所有行，dp[-1][-1] 不等于目標(biāo)值，則說明不能劃分，返回 False。

時間復(fù)雜度為 O(n^2)，空間復(fù)雜度為 O(n*(sum(nums) // 2))。

Python3 實現(xiàn)：

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        lens = len(nums)
        if lens == 1:
            return False
        tot = sum(nums)
        if tot % 2 == 1:
            return False
        tar = tot // 2
        dp = [[0] * (tar+1) for _ in range(lens+1)]
        for i in range(1, lens + 1):
            for j in range(1, tar + 1):
                if j < nums[i-1]:
                    dp[i][j] = dp[i-1][j]
                else:
                    dp[i][j] = max(dp[i-1][j], dp[i-1][j-nums[i-1]] + nums[i-1])
            if dp[i][j] == tar:  # 更新完一行就應(yīng)該判斷一下
                return True
        return False

print(Solution().canPartition([2,5,3,4]))  # True
print(Solution().canPartition([5,1,3,5]))  # False

注：這類題目，即物品（數(shù)組元素）有存在與否兩種狀態(tài)的題目，都可以用01-背包的思想和解法進行解決。如果每件物品可以放若干件，那就變成多重背包問題了。

方法3：使用貪心 + DFS回溯法求解（beats 100%）：

其實這道題和 Leetcode 【Greedy+DFS】473. Matchsticks to Square 以及 Leetcode 【Greedy+DFS】698. Partition to K Equal Sum Subsets 幾乎一模一樣，只需要將 Leetcode 473 中的 4 改成 2 即可。

Python3 實現(xiàn)：

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        def search(ind):  # ind為nums下標(biāo)，從0開始
            if ind == N:  # 將nums全部數(shù)填入targets，返回True
                return True
            for i in range(2):  # 對于每一個targets
                if targets[i] >= nums[ind]:  # 保證targets該位置的數(shù)字>=放置的數(shù)字
                    targets[i] -= nums[ind]
                    if search(ind + 1):
                        return True
                    targets[i] += nums[ind]  # 回溯
            return False    
        
        div, mod = divmod(sum(nums), 2)
        if mod != 0:
            return False
        nums.sort(reverse=True)  # 降序排序可以減少遞歸次數(shù)(親測)
        if not nums or nums[0] > div:  # 數(shù)組可能為空
            return False
        N = len(nums)
        targets = [div] * 2  # 2個大小為目標(biāo)數(shù)的桶
        return search(0)

這個代碼運行只有 36ms，遠遠好于上述兩種方法，beats 100% 的提交。