题解 | 分割等和子集

方法一：递归回溯

相当于数组中能否凑到s//2

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param nums int整型一维数组 
# @return bool布尔型
#
class Solution:
    def partition(self , nums: List[int]) -> bool:
        # write code here 递归回溯可能超内存，请注意！！！编译其中也可用缓存函数cache试
        def dfs(i: int, x: int) -> bool:
            if i < 0:
                return x == 0
            return x >= nums[i] and dfs(i - 1, x - nums[i]) or dfs(i - 1, x)
        s = sum(nums)
        return s % 2 == 0 and dfs(len(nums) - 1, s // 2)
	  #或者
        '''s, n = sum(nums), len(nums)
        def dfs(i,x):
            if i>=n:
                return x==0
            return x>=nums[i] and dfs(i+1,x-nums[i]) or dfs(i+1,x)
        return s % 2 == 0 and dfs(0, s // 2)'''

方法二：动态规划

相当于状态转移，看是否能从0转移到s//2（偶数）

		#动态规划也可以做本题
        s = sum(nums)
        if s%2:
            return False
        s //= 2
        dp = [False]*(s+1)
        dp[0] = True
        for x in nums:#相当于状态转移，看是否能从0转移到s//2
            for i in range(s,x-1,-1):#若x-1>=s,则循环体内代码不会被执行
                dp[i] = dp[i] or dp[i-x]
        return dp[-1]

力扣大神的专业解答（本人代码看代码段及注释。）：

三种写法：记忆化搜索 / 递推 / bitset 优化（Python/Java/C++/C/Go/JS/Rust）