思路：動態(tài)規(guī)劃 dp[i][j]前i個數(shù)中能否組成和為j的子數(shù)組
class Solution:
def canPartition(self, nums: List[int]) -> bool:
size = len(nums)
s = sum(nums)
if s & 1 == 1:
return False
target = s // 2
dp = [[False for _ in range(target + 1)] for _ in range(size)]
for i in range(target + 1):
dp[0][i] = False if nums[0] != i else True
for i in range(1, size):
for j in range(target + 1):
if j >= nums[i]:
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]
else:
dp[i][j] = dp[i - 1][j]
return dp[-1][-1]
判斷是否可以把一組數(shù)字分為兩堆虽画，兩堆數(shù)字的和相等
思路：首先要判斷所有數(shù)字的和是不是偶數(shù)溜哮，然后我們使用一個長度為2的數(shù)組進(jìn)行保存我們要平分得到的target拜姿，這么做是我們可以通過使用-，+兩種操作來跳過一些數(shù)字。
class Solution:
def canPartition(self, nums):
"""
:type nums: List[int]
:rtype: bool
"""
_sum = sum(nums)
div, mod = divmod(_sum, 2)
if mod or max(nums) > div: return False
nums.sort(reverse = True)
target = [div] * 2 #一開始將 target 數(shù)組設(shè)為目標(biāo)值，然后減去 nums 里的每個數(shù)
return self.dfs(nums, 0, target)
def dfs(self, nums, index, target):
for i in range(2):
if target[i] >= nums[index]:
target[i] -= nums[index]
if target[i] == 0 or self.dfs(nums, index + 1, target): return True
target[i] += nums[index]
return False
代碼中烫饼，根據(jù)下一層 return 的True/False 來定義當(dāng)前層遞歸 return 的True/False，如果下一層 return 的是 False试读，再加回當(dāng)前的數(shù)字消除前面-num[index]的影響杠纵。
