416. Partition Equal Subset Sum
416. Partition Equal Subset Sum
首先我們要確立目標，目標是給定一個陣列能不能分成兩個子集合，讓這兩個子集合的總和相等。
第一個要去想的地方比較簡單，既然兩個子集合要相等，那一個子集合一定是原陣列總和的一半，我們的目標就是要找到一個一個子集合，其總和是原陣列總和的一半。
另外，有可能原陣列的元素總和是奇數：例如：[1, 2, 1, 1] 這樣的陣列總和是 5 ，一定不會有辦法分成兩個集合，所以可以先用這樣的方式去剪枝（把所有總和為奇數的直接排除掉）。
接著是要怎麼選擇，每一個元素我們都可以有「選」或是「不選」這兩種方式，如果選的話，我們的目標就會減少當下的數值，如果不選的話，目標並不會改變，一直到如果我們選了最後一個數字，如果最後目標剛好等於 0 ，那就是我們透過選擇，找到了目標。
這樣的關係可以用一個遞迴的方式來呈現。
遞迴
class Solution:
def canPartition(self, nums: List[int]) -> bool:
total = sum(nums)
if total % 2 != 0:
return False
def helper(i, target):
if i == len(nums) - 1:
return target == 0
else:
return helper(i + 1, target - nums[i]) or helper(i + 1, target)
return helper(0, total//2)既然遞迴的方式已經寫好了，上面這個函式很明顯的存在著重疊的子問題，例如最後一個位置的「選」或「不選」，在前面幾個元素在做選擇時，會一直重複的計算，因此可以用記憶法，來記憶著已經做過的選擇。而每個位置的選擇或不選擇，可以透過當前位置與目標來決定。
自頂向下
class Solution:
def canPartition(self, nums: List[int]) -> bool:
total = sum(nums)
if total % 2 != 0:
return False
memo = {}
def helper(i, target):
if (i, target) in memo:
return memo[(i, target)]
if i == len(nums) - 1:
return target == 0
else:
memo[(i, target)] = helper(i + 1, target - nums[i]) or helper(i + 1, target)
return memo[(i, target)]
return helper(0, total//2)自底向上
一直以來我都覺得自底向上比較難想到，這題也是不太好想。
原陣列的每個位置都會有選擇或是不選擇兩種，自底向上的想法是，如果我們知道第 i 的位置在選擇的時候，是不是可以達到某個比我們的目標還要小的數值。
文字敘述很抽象，換成一個數學的例子就是，現在最後的目標是 5 ，前一個位置如果已經可以達到目標 5 了，那我這個位置就不用選擇，如果我的當前值是 2 ，那在前一個位置如果可以達到 5 - 2 = 3 ，那我就要選擇當前位置的元素，這一串選擇就是 L20 在做的事情。
一開始的 base case 則是如果說一開始的目標就是 0 ，那不管有沒有選都是符合條件了。
class Solution:
def canPartition(self, nums: List[int]) -> bool:
total = sum(nums)
if total % 2 != 0:
return False
M = len(nums)
N = total // 2
dp = [[False] * (N + 1) for _ in range(M+1)]
for i in range(M+1):
dp[i][0] = True
for i in range(1, M+1):
for j in range(1, N+1):
if j - nums[i - 1] < 0:
dp[i][j] = dp[i - 1][j]
else:
dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i-1]]
return dp[M][N]