416. 分割等和子集 非动态规划解法

解题思路

高票答案的思路是开一个target+1长度的数组dp，依次记录能够组合出现的和。其实问题可以转化为生成所有可能的和，并在出现目标和的时候及时停止。我们可以用一个集合rec记录生成的和，一开始rec中只有0；每次遍历nums的一个数字n，并更新rec（每个rec记录的和加上新的数字n，并添加进rec中）。
这种从无到有构建的过程类似于递归解法转化为递推解法，根据DP转移方程自底向上构建状态。这里的状态就是所有可能的和。
有所感悟，DP是一种强大的思考方式，但并不一定是目的，经过DP处理过的问题也许可以转化为非DP的处理方法。（当然也可以说本质上还是DP，因为由DP推导所得）

代码

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        s = sum(nums)

        if not nums or len(nums)<2 or s%2:  # 不能被2整除必为False
            return False

        ans = False

        target = s//2

        rec = {0}

        for n in nums:
            for t in tuple(rec):
                rec.add(t+n)
            if target in rec:
                return True

        return False