题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个只有正整数的非空数组，要求是否能取出两个子集且这两个子集和相等。

思路分享

  • 本质其实是问是否能找到一个和相当于总和一半的子集。首先总和为奇数不可能达成，然后尝试划分一下子问题。

  • 对于本题，可以采用“选或不选”的思路，建立的数组f[i][j]的含义是，从数组的前 i 个数字选出合适的子集和为 j。

  • 从后向前（从前向后应当也行）每个数字考虑选的时候，就把总和减去这个对应位置数字，同时下标减一，这样就得到了下一个子问题；不选，就直接下标减一，考虑下个数字，这就是另一个子问题。

  • 子问题不断划分后，就要考虑边界，对于上面从后向前的顺序，最后下标到 0，如果此时剩余和为零，说明刚好满足，返回 True，其余情况不满足则 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
32
33
34
class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        # 递推
        sum_all = sum(nums)
        if sum_all % 2 == 1:
            return False
        sum_all //= 2
        n = len(nums)
        f = [[False] * (sum_all + 1) for _ in range(n+1)]
        f[0][0] = True
        for i, x in enumerate(nums):
            for j in range(sum_all+1):
                f[i+1][j] = f[i][j] or (j >= x and f[i][j-nums[i]])
        return f[n][sum_all]

        # f[i][j] = f[i-1][j] or f[i-1][j-nums[i]]

        
        # 记忆化搜索
        # sum_all = sum(nums)
        # if sum_all % 2 == 1:
        #     return False

        # n = len(nums)

        # @cache
        # def dfs(index:int, sum_cur:int) -> bool:
        #     # print(str(index) + " " + str(sum_cur))
        #     if index <= 0:
        #         return True if sum_cur == 0 else False
        #     return (nums[index] <= sum_cur and dfs(index-1, sum_cur-nums[index]) or dfs(index-1, sum_cur))
            

        # return dfs(n-1, sum_all//2)