分割等和子集
Problem: 416. 分割等和子集
思路
我選擇使用動態規劃的方法來解題。我們需要判斷是否可以將數組分割成兩個子集，使得這兩個子集的和相等。這個問題可以轉化為在數組中找到一個子集，使得其和等于數組總和的一半。
解題過程
- 首先，我們計算數組的總和
total。如果total是奇數，那么我們無法將其分成兩個和相等的子集，因此直接返回False。 - 接下來，我們將目標和
target定為total // 2。 - 初始化一個二維布爾數組
dp，其中dp[i][j]表示前i個元素是否可以組成和為j的子集。 - 設置初始條件：
dp[i][0]為True，因為和為0的子集總是可以通過不選取任何元素來實現。 - 遍歷數組，更新
dp數組：- 如果當前元素
nums[i]小于等于目標和j，則dp[i][j]可以由兩種情況得到：不包含當前元素（即dp[i-1][j]）或包含當前元素（即dp[i-1][j-nums[i]]）。 - 如果當前元素
nums[i]大于目標和j，則dp[i][j]只能由不包含當前元素的情況得到，即dp[i-1][j]。
- 如果當前元素
- 最后，檢查
dp[n-1][target]的值，判斷是否可以將數組分割成兩個和相等的子集。
復雜度
- 時間復雜度:
，其中
n是數組的長度，target是數組總和的一半。 - 空間復雜度:
dp。
Code
from typing import Listclass Solution:def canPartition(self, nums: List[int]) -> bool:n = len(nums)if n < 2:return Falsetotal = sum(nums)if total & 1:return Falsetarget = total // 2if max(nums) > target:return Falsedp = [[False] * (target + 1) for _ in range(n)]for i in range(n):dp[i][0] = Truedp[0][nums[0]] = Truefor i in range(1, n):for j in range(1, target + 1):if j >= nums[i]:dp[i][j] = dp[i-1][j] | dp[i-1][j-nums[i]]else:dp[i][j] = dp[i-1][j]return dp[n-1][target]
)
