# **Leetcode筆記(Partition Equal Subset Sum)**

:::info
:information_source: 題目 : Partition Equal Subset Sum, 類型 : dynamic programming , 等級 : medium
日期 : 2023/06/13，2023/09/04，2025/03/02
:::

### 嘗試
2023/09/04
可以把題目簡化成能不能在給定list中，"找到list / 2"的數值
這種看"能不能在subset組成"的加法，基本上都是用樹枝，一邊加一邊不加

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        if sum(nums) % 2:
            return False
        
        half = sum(nums) // 2

        # 初始化
        record = set()
        record.add(0)

        for n in nums:
            recordOld = record.copy()
            for nOld in recordOld:
                record.add(nOld + n)
            
        return True if half in record else False

2025/03/02

class Solution:
    def canPartition(self, nums: List[int]) -> bool:
        total = sum(nums)
        if total % 2:
            return False

        half = total // 2
        dp = [False] * (half + 1)
        dp[0] = True

        for n in nums:
            dp_new = dp[:] # 確保當前的dp 不受當前n影響
            for j in range(1, half + 1):
                if n <= j:
                    dp_new[j] = dp_new[j] or dp[j - n]
            dp = dp_new
        
        return dp[half]

---
### **優化**
首先要先檢查整串數組是否為偶數，是奇數的話直接不用談
以下dp[i][j]，整數j為目標，考慮每個數字[0, i]

狀態轉移方程式
**1.不選擇num[i]
dp[i][j] = dp[i - 1][j]**
**2.選擇num[i]
若num[i] = j 則dp[i][j] = True
若num[i] < j 則dp[i][j] = dp[i - 1][j - num[i]]**

**1. j 小於 nums[i]
不選擇該元素，dp[i][j] = dp[i - 1][j]**
**2. j 大於等於 nums[i]
如果選擇該元素，則 dp[i - 1][j - nums[i]]
如果不選擇該元素，則 dp[i - 1][j]**

記得 : 初始化把dp[i][0]全部設定為True，如果總和為0，則不選擇任何元素即可滿足條件。

時間複雜度：
- 填充動態規劃矩陣 `dp` 的時間複雜度為 O(n * target)。

空間複雜度：
- 使用的額外空間是動態規劃矩陣 `dp`，其大小為 (n+1) * (target+1)。
- 因此，空間複雜度為 O(n * target)。

class Solution:
    def canPartition(self, nums):
        # 奇數加總必定錯誤
        if sum(nums) % 2 != 0:
            return False
        target = int(sum(nums) / 2)

        dp = [[False] * (target + 1) for _ in range(len(nums))]

        for i in range(len(nums)):
            dp[i][0] = True

        for i in range(len(nums)):
            for j in range(1, target + 1):
                if j < nums[i]:  # 沒有辦法選擇
                    dp[i][j] = dp[i - 1][j]
                else:  # 大於或等於
                    dp[i][j] = dp[i - 1][j] or dp[i - 1][j - nums[i]]

        return dp[len(nums) - 1][target]

---

**:warning: 錯誤語法**
:::warning

:::

**:thumbsup:學習**
:::success

:::

**思路**

**講解連結**
https://www.youtube.com/watch?v=FTrEHdKJzpc&t=291s&ab_channel=LeetCode%E5%8A%9B%E6%89%A3
Provided by. LeetCode 力扣

###### tags: `dynamic programming` `medium` `leetcode` `值得再想`