Leetcode 416：分割等和子集（最详细的解法！！！）_等和分割子集解题思路

给定一个只包含正整数的非空数组。是否可以将这个数组分割成两个子集，使得两个子集的元素和相等。

注意:

1. 每个数组中的元素不会超过 100
2. 数组的大小不会超过 200

示例 1:

输入: [1, 5, 11, 5]
输出: true
解释: 数组可以分割成 [1, 5, 5] 和 [11].
1
2
3

示例 2:

输入: [1, 2, 3, 5]
输出: false
解释: 数组不能分割成两个元素和相等的子集.
1
2
3

解题思路

这个问题和Leetcode 473：火柴拼正方形和Leetcode 698：划分为k个相等的子集是一样的，直接将Leetcode 698中的k赋值为2即可。

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s, n = sum(nums), len(nums)
        if s %2 :
            return False
        
        t = s//2
        nums.sort(reverse=True)
        vis = [0] * n
        
        def dfs(cur, u, p):
            if u == 2: return True
            if cur == t: return dfs(0, u + 1, 0)
            
            i = p
            while i < n:
                if vis[i] or (cur + nums[i] > t): 
                    i += 1
                    continue
                    
                vis[i] = 1
                if dfs(cur + nums[i], u, i + 1): return True
                vis[i] = 0
                
                if not cur or cur + nums[i] == t: return False 
                
                j = i
                while j < n and nums[i] == nums[j]: j += 1 
                i = j - 1
                i += 1
            return False
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题，希望大家指出！！！